题目

链接：leetcode链接

思路分析（双指针）

这道题目与上一道题，求有效三角形的个数，十分类似，都是使用双指针算法来解决问题。

先进行排序，然后利用单调性进行调整，逐步逼近正确答案。

我们先固定一个数，记作target，则只需要寻找两个数，使这两个数的和为负target即可。

不妨将target固定位最大值，将需要的两个数在target的左边区间进行寻找，即在小于target的范围里寻找，这时利用双指针，记作left，right，从两侧向中间逼近即可。

会出现以下三种情况：
a、left + right + target > 0
这说明right大了，需要 --right，继续寻找
b、left + right + target < 0
这说明left小了，需要 ++left，继续寻找
c、left + right + target == 0
符合要求，保存下来，继续寻找，
注意：题目有要求不能重复，所以，我们可以在找到了符合要求的三元组后，跳过相同元素再继续寻找，这样，就可以避免重复的三元组。(当然使用set等去重也可以）

同理，target也需要进行去重。

代码

vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> a;for(int i = nums.size()-1;i>=2;--i){int left = 0,right = i-1;while(left < right){int sum = nums[left] + nums[right] + nums[i];if(sum == 0){a.push_back({nums[left],nums[right],nums[i]});//这两个while是去重while(nums[left] == nums[left + 1] && left < right) ++left;while(nums[right] == nums[right - 1] && left < right) --right;//这个是去完重后寻找下一个三元组left++,right--;//}else if(sum > 0) --right;else ++left;}//for循环里面已经有一个--i了，这里一个--i就可以去重并且走向下一个三元组while(nums[i] == nums[i-1] && i>=3) --i;}return a;}

另一道相似的题----四数之和

方法几乎一样，只是多套一层循环。

这道题目有一点很坑的地方，题目中target是int类型，但是四数之和有可能是超过int类型的范围的，需要强转。

代码附上

 vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> a;for(int i = nums.size() - 1;i >= 3;--i){for(int j = i - 1;j >= 2;--j){int left = 0, right = j - 1;while(left < right){long long sum = (long long)nums[left] + nums[right] + nums[i] + nums[j];if(sum == (long long)target){a.push_back({nums[left],nums[right],nums[i],nums[j]});while(nums[left] == nums[left + 1] && left < right){++left;}while(nums[right] == nums[right - 1] && left < right){--right;}++left;--right;}else if(sum < (long long)target){++left;}else{--right;}}while(nums[j] == nums[j - 1] && j >= 3){--j;}}while(nums[i] == nums[i - 1] && i >= 4){--i;}}return a;}