三数之和-力扣
这道题在使用哈希表来做时，做的很吃力，对重复的去除很费劲。
- 首先是对i的去重，不能使用nums[i] == nums[i+] 这样的条件去判断，这会遗漏掉类似[-1, -1 , 2]这样的解
- 其次是对j的去重， 对j的去重是为了防止类似[-4, 2, 2, 2], [0, 0, 0, 0]这类数组的重复的解的出现，如果使用nums[j] == nums[j +1] && nums[j+1] == nums[j+2], 此时for循环需要改为 j < nums.size() - 2，但这样就会漏掉数组的最后两个元素。
- 哈希表set每个 i 需要重新创建，否则之前存在set中的值会影响判断，造成重复的解
- 三数之和的求解，是对数组进行遍历，然后将问题分解为 n 个两数之和去求解。
代码如下：
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> threeSum;int i,j,k;sort(nums.begin(), nums.end());for(i = 0; i < nums.size(); i++){if(nums[i] > 0){return threeSum;}if(i > 0 && nums[i] == nums[i - 1]){continue;}unordered_set<int> s;for(j = i + 1; j < nums.size(); j++){if(j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]){continue;}k = 0 - nums[i] - nums[j];if(s.find(k) != s.end()){threeSum.push_back( {nums[i], nums[j], k} );s.erase(k);} else {s.insert(nums[j]);}}}return threeSum;}
};
第二种写法是只用双指针的写法，对排序后的升序数组，left指向i+1，right指向nums.size() - 1。
- 当三个数相加小于0时，left++
- 当三个数相加大于0时，right–
- 当三个数相加等于0时，则对left和right进行去重，然后同时左右收缩
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> threeSum;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i++){if(nums[i] > 0){return threeSum;}if(i > 0 && nums[i] == nums[i - 1]){continue;}int left = i + 1;int right = nums.size() - 1;while(left < right){if(nums[i] + nums[left] + nums[right] == 0){threeSum.push_back({nums[i], nums[left], nums[right]});while(right > left && nums[right] == nums[right - 1]){right--;}right--;while(right > left && nums[left] == nums[left + 1]){left++;}left++;}else if(nums[i] + nums[left] + nums[right] < 0){left++;}else {right--;}}}return threeSum;}
};