首页 > 代码库 > 《Cracking the Coding Interview》——第17章：普通题——题目12

《Cracking the Coding Interview》——第17章：普通题——题目12

2024-07-02 00:18:08   221人阅读

2014-04-29 00:04

题目：给定一个整数数组，找出所有加起来为指定和的数对。

解法1：可以用哈希表保存数组元素，做到O(n)时间的算法。

代码：

 1 // 17.12 Given an array of integers and target value, find all pairs in the array that sum up to the target.
 2 // Use hash to achieve O(n) time complexity. Duplicates pairs are skipped.
 3 #include <cstdio>
 4 #include <unordered_map>
 5 #include <vector>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     vector<int> v;
11     unordered_map<int, int> um;
12     int n, i;
13     int x, y;
14     int target;
15     
16     while (scanf("%d", &n) == 1 && n > 0) {
17         scanf("%d", &target);
18         
19         v.resize(n);
20         for (i = 0; i < n; ++i) {
21             scanf("%d", &v[i]);
22         }
23         
24         // duplicate pairs are skipped
25         for (i = 0; i < n; ++i) {
26             um[v[i]] = um[v[i]] + 1;
27         }
28         
29         unordered_map<int, int>::iterator it, it2;
30         for (it = um.begin(); it != um.end(); ++it) {
31             x = it->first;
32             y = target - x;
33             if (x > y) {
34                 continue;
35             }
36             
37             --it->second;
38             if ((it2 = um.find(y)) != um.end() && it2->second > 0) {
39                 printf("(%d, %d)\n", x, y);
40             }
41             ++it->second;
42         }
43         
44         v.clear();
45         um.clear();
46     }
47     
48     return 0;
49 }

解法2：先将数组排序，然后用两个iterator向中间靠拢进行扫描。总体时间是O(n * log(n))。

代码：

 1 // 17.12 Given an array of integers and target value, find all pairs in the array that sum up to the target.
 2 // O(n * log(n) + n) solution.
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <vector>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     vector<int> v;
11     int n, i;
12     int ll, rr;
13     int target;
14     
15     while (scanf("%d", &n) == 1 && n > 0) {
16         scanf("%d", &target);
17         
18         v.resize(n);
19         for (i = 0; i < n; ++i) {
20             scanf("%d", &v[i]);
21         }
22         sort(v.begin(), v.end());
23         ll = 0;
24         rr = n - 1;
25         
26         int sum;
27         while (ll < rr) {
28             sum = v[ll] + v[rr];
29             if (sum < target) {
30                 while (ll + 1 < rr && v[ll] == v[ll + 1]) {
31                     ++ll;
32                 }
33                 ++ll;
34             } else if (sum > target) {
35                 while (rr - 1 > ll && v[rr] == v[rr - 1]) {
36                     --rr;
37                 }
38                 --rr;
39             } else {
40                 printf("(%d, %d)\n", v[ll], v[rr]);
41                 while (ll + 1 < rr && v[ll] == v[ll + 1]) {
42                     ++ll;
43                 }
44                 ++ll;
45             }
46         }
47         
48         v.clear();
49     }
50     
51     return 0;
52 }

 


联系
我们