编程之美2.12 快速寻找满足条件的两个数

问题描述：

能否快速找到一个数组中的两个数字，让这两个数字之和等于一个给定的数字，为了简化起见，我们假设这个数组中肯定存在这样一组或以上符合条件的解。这里我们只考虑一种解

的情况。

解法：

1. 暴力解法------O(n^2)

2. 排序+二分查找------O(nlogn)

3. hash表查找------O(n)

4. 排序+收尾相加移动法-------O(nlogn)

具体思路和代码：

1. 暴力解法------O(n^2)

思路：第一层循环控制一个变量A[i]不变，在另一层循环中查找Sum-A[i].

代码：

 1 vector<int> s1(int A[], int n, int sum)
 2 {
 3     for(int i = 0; i < n; i++)
 4     {
 5         vector<int> v;
 6         v.push_back(A[i]);
 7         int m = sum - A[i];
 8         for(int j = 0; j < n; j++)
 9         {
10             if(A[j] == m)
11             {
12                 v.push_back(A[j]);
13                 return v;
14             }
15         }
16     }
17 }

2. 排序+二分查找------O(nlogn)

思路：先对数组进行排序（nlogn），

然后固定住一个数值，利用二分查找的方式找到另一个（nlogn）

代码：

 1 void exchange(int A[], int i, int j)
 2 {
 3     int temp = A[i];
 4     A[i] = A[j];
 5     A[j] = temp;
 6 }
 7 
 8 int partition(int A[], int p, int r)
 9 {
10     int x = A[r];
11     int i = p-1;
12     for(int j = p; j < r; j++)
13     {
14         if(A[j] <= x)
15         {
16             i++;
17             exchange(A, i, j);
18         }
19 
20     }
21     exchange(A, i+1, r);
22     return i+1;
23 }
24 
25 
26 void QuickSort(int A[], int p, int r)
27 {
28     if(p >= r)
29         return;
30     else
31     {
32         int t = partition(A, p, r);
33         QuickSort(A, p, t-1);
34         QuickSort(A, t+1, r);    
35     }
36     
37 }
38 
39 int binSearch(int A[], int p, int r, int o)
40 {
41     if(p > r)
42         return -1;
43 
44     int mid = (p + r) / 2;
45     if(o == A[mid])
46         return mid;
47 
48     else
49     {
50         if(o < A[mid])
51             return binSearch(A, p, mid-1, o);
52         else
53             return binSearch(A, mid+1, r, o);
54     }
55 
56 }
57 
58 vector<int> s2(int A[], int n, int sum)
59 {
60     for(int i = 0; i < n; i++)
61     {
62         vector<int> v;
63         v.push_back(A[i]);
64         int m = binSearch(A, 0, n-1, sum-A[i]);
65         v.push_back(A[m]);
66         return v;
67     }
68 }

3. hash表查找------O(n)

思路：空间换时间利用hash表将数据一一存储，这里涉及到hash函数的设计。

　　　第一层循环，固定住A[i].--------O(n)

在hash表中查找Sum-A[i].-------O(1)

这边代码省略，主要是设计hash函数，怎样一一映射。

4. 排序+收尾相加移动法-------O(nlogn)

思路：先对数组进行排序（nlogn），

然后对数值进行收尾相加，若和大于sum，尾巴往前移动。

　　　　若和小于sum，头部往后移动。

代码：

 1 vector<int> s3(int A[], int n, int sum)
 2 {
 3     for(int i = 0, j = n-1; i <j;)
 4     {
 5         vector<int> v;
 6         if(A[i] + A[j] == sum)
 7         {
 8             v.push_back(A[i]);
 9             v.push_back(A[j]);
10         }
11         else
12         {
13             if(A[i] + A[j] > sum)
14                 j--;
15             else
16                 i++;
17         }
18         return v;
19     }
20 }