寻找和为定值的两个数
寻找和为定值的两个数
题目描述：
输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。如果有多对数字的和等于输入的数字，输出任意一对即可。
分析和解法：
解法一：暴力穷举
直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。
源代码如下：
#include <iostream>
using namespace std;
int main()
{
int a[100];
int i = 0;
char ch;
while((ch = cin.get()) != '\n') //此处也可以用 cin.peek() ，只预读，不取出
{
cin.unget();
cin >> a[i++];
}
int sum;
cin >> sum;
int j;
for (j = 0; j < i - 1; j++)
for (int k = j + 1; k < i; k++)
{
if (a[j] + a[k] == sum)
{
cout << a[j] << " " << a[k] << endl;
return 0;
}
}
if (j = i - 1) cout << "None" << endl;
return 0;
}
分析：时间复杂度为 O（n ^ 2）。
解法二：排序 + 二分查找
题目相当于，对每个 a[i] ，查找 sum - a[i] 是否也在原始序列中。我们可以先排序，再用二分查找去查找 sum - a[i] 。
源代码如下：
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int Compare(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
int main()
{
int a[100];
int i = 0;
char ch;
while((ch = cin.get()) != '\n') //此处也可以用 cin.peek() ，只预读，不取出
{
cin.unget();
cin >> a[i++];
}
int sum;
cin >> sum;
qsort(a, i, sizeof(int), Compare);
int j;
for (j = 0; j < i; j++)
{
if (binary_search(a, a + i, sum - a[j]))
{
cout << a[j] << " " << sum - a[j] << endl;
return 0;
}
}
if (j = i) cout << "None" << endl;
return 0;
}
分析：时间复杂度为 O（n logn）。
解法三：前后指针扫描
此种解法针对有序的序列可以做到 O（n）。无序的序列要求先进行排序。
根据前面的分析，a[i] 在序列中，如果 a[i] + a[k] = sum 的话，那么 sum - a[i]（a[k]）也必然在序列中。 举个例子，如下：
原始序列：
1、 2、 4、 7、11、15
用输入数字 15 减一下各个数，得到对应的序列为：
14、13、11、8、4、 0
第一个数组以一指针 i 从数组最左端开始向右扫描，第二个数组以一指针 j 从数组最右端开始向左扫描，如果第一个数组出现了和第二个数组一样的数，即 a[i] = a[j]，就找出这俩个数来了。 如上，i，j 最终在第一个和第二个序列中找到了相同的数 4 和 11 ，所以符合条件的两个数，即为 4 + 11 = 15。
源代码如下：
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int Compare(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
int main()
{
int a[100];
int i = 0;
while(cin.get() != '\n') //此处也可以用 cin.peek() ，只预读，不取出
{
cin.unget();
cin >> a[i++];
}
int sum;
cin >> sum;
qsort(a, i, sizeof(int), Compare);
int b[100];
for (int k = 0; k < i; k++)
b[k] = sum - a[k];
int j;
for (j = 0; j <= i/2; )
{
if (a[j] == b[i - 1])
{
cout << a[j] << " " << sum - a[j] << endl;
break;
}
if (a[j] < b[i - 1])
{
j++;
continue;
}
if (a[j] > b[i - 1])
{
i--;
continue;
}
}
if (j > i/2) cout << "None" << endl;
return 0;
}
分析：此种解法针对有序序列的时间复杂度为 O（n），空间复杂度为 O（n）。如果是无序序列，则需要先排序。
解法四：哈希表
两数与定值的一半的差的绝对值相等。
利用这一性质，我们建立起哈希映射关系。其中考虑到定值为奇数时，a[k] - sum/2 会取整可能影响结果，所以我们可以用 2 * a[k] - sum 代替。
源代码如下：
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int a[100];
int i = 0;
cout << "输入数的范围为 -99 ~ 99: " << endl;
while(cin.get() != '\n') //此处也可以用 cin.peek() ，只预读，不取出
{
cin.unget();
cin >> a[i++];
}
int sum;
cin >> sum;
int b[200] = {}; //初始化全部成员为 0
for (int k = 0; k < i; k++)
b[abs(2 * a[k] - sum)]++; //两数与定值的一半的差的绝对值相等
int j;
for (j = 0; j < 200; j++)
{
if (b[j] > 1)
{
cout << (sum + j) / 2 << " " << (sum - j) / 2 << endl;
break;
}
}
if (j > 200) cout << "None" << endl;
return 0;
}
分析：这种解法不需要序列有序，时间复杂度还为 O（n），但是需要以空间换取时间。
解法总结
不论原序列是有序还是无序，解决这类题有以下三种办法：
- 1、二分（若无序，先排序后二分），时间复杂度总为 O(N log N)，空间复杂度为 O（1）；
- 2、扫描一遍 X - S[i] 映射到一个数组或构造 hash 表，时间复杂度为 O(N)，空间复杂度为 O(N)；
- 3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序 O(N)，无序 O(N log N + N) = O(N log N)，空间复杂度都为 O(1)。
所以，要想达到时间 O(N)，空间 O(1) 的目标，除非原数组是有序的（指针扫描法），不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间 O(Nlog N)，空间O(1)），或映射或 hash（时间 O(N)，空间 O(N)）。时间或空间，必须牺牲一个，达到平衡。
综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时间复杂度O(N)，空间复杂度O(1)。否则，如果要排序的话，时间复杂度最快当然是只能达到O(N log N)，空间O(1)则不在话下。
特别注意：
- 数组初始化：
- 声明的全局数组会被编译器全部初始化为 0
- 局部数组：
1. 成员全部初始化： int myArray[10] = { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }; 2. 将缺省的成员置为 0: int myArray[10] = { 1, 2 }; //initialize to 1,2,0,0,0... 3. 初始化全部成员为 0: int myArray[10] = { 0 }; //all elements 0 4. 在 C++中, 空的初始化也会将全部成员置为 0: int myArray[10] = {}; //all elements 0 in C++ 5. 如果声明为 static，则全部成员默认为 0，如果你不去手动初始化的话。 static int myArray[10]; //all elements 0 6. for 循环，一个一个赋值 int myArray[10]; for (int i = 0; i < 10; i++) myArray[i] = 0; 7. memset(数组名，准备初始化的值，数组的大小)，memset 是以字节为单位对数组所在内存进行赋值的 memset(myArray, 0, sizeof(myArray));
参考资料：《编程之法》The Art of Programming By July
