17.12 Design an algorithm to find all pairs of integers within an array which sum to a specified value.
这道题实际上跟LeetCode上的Two Sum很类似，但是不同的是，那道题限定了只有一组解，而这道题说可以有很多组符合要求的解，那么我们先来看一种使用哈希表的解法，这种解法的时间复杂度是O(n)，空间复杂度是O(1)，思路是用哈希表建立每个数字和其下标之间的映射，遍历整个数字，如果target减去当前数字的值在哈希表中存在，那么返回这一对结果，然后更新当前数字在哈希表中的映射值，参见代码如下：
解法一：
void find_pairs(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); ++i) { if (m.count(target - nums[i])) { cout << nums[i] << " " << nums[m[target - nums[i]]] << endl; } m[nums[i]] = i; } }
下面这种方法是利用了双指针的思路，我们首先要把数组排个序，然后左右两个指针向中间移动，如果当前两个指针指的数加起来正好等于target，则找到了一对结果，如果大于target，那么我们将右指针左移一位，这样值能减小一些，如果和小于target，则把左指针右移一位，这样和能增大一些，参见代码如下：
解法二：
void find_pairs(vector<int> nums, int target) { sort(nums.begin(), nums.end()); int left = 0, right = nums.size() - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { cout << nums[left] << " " << nums[right] << endl; ++left; --right; } else if (sum > target) { --right; } else { ++left; } } }
本文转自博客园Grandyang的博客，原文链接：和为特定数[CareerCup] 17.12 Sum to Specific Value ，如需转载请自行联系原博主。
