15. 3Sum 找到数组中三数之和为给定值的组合

找到数组中三数之和为给定值的组合。

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

思考：求解三数之和，会先联想到求解两数之和。先来回忆一下两数之和怎么求解。方法1，使用unordered_map存放数组值和下标，再遍历数组从寻找是否又差值，有就找到一个组合。使用unordered_map存放下标，是为了这种case考虑，如sum=2, 数组中有一个1， 这时，再找就仍然找的是这个1就不对了。方法2. 在遍历是向set中存放没有配对的数值，如果可以从set中找到，那就找到一个组合了。这种方法不用存放下标。方法3.对原有数组进行排序，在用两个指针，low和high指针。如果它们的和大于sum，就high--，反之，low++。 用这三种方法进行拓展都可以解决3-sum问题。不过使用第三种方法最好。

解法：

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int low = i + 1; int high = nums.size() - 1; while (low < high) { int three_sum = nums[i] + nums[low] + nums[high]; if (three_sum == 0) { res.push_back({nums[i], nums[low], nums[high]}); ++low; --high; // 注意防止重复的结果 while (low < high && nums[low] == nums[low - 1]) { ++low; } while (low < high && nums[high] == nums[high + 1]) { --high; } } else if (three_sum < 0) { ++low; } else { --high; } } } return res; }