力扣hot100——三数之和（双指针）

题目：三数之和

排序 + 双指针

本题的难点在于如何去除重复解。

算法流程：

1、特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
2、对数组进行排序。
3、遍历排序后数组：
（1）若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
（2）对于重复元素：跳过，避免出现重复解
（3）令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
若和大于 0，说明 nums[R] 太大，R 左移
若和小于 0，说明 nums[L] 太小，L 右移作者：吴彦祖
链接：https://leetcode.cn/problems/3sum/solutions/39722/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回空数组if(nums.size()<3){return vector<vector<int>>();}int l,r;vector<vector<int>> result; //对数组进行排序。sort(nums.begin(), nums.end());for (int i = 0; i< nums.size(); i++){l=i+1;r = nums.size()-1;//若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。if (nums[i]>0){return result;}//难点：对于重复元素：跳过，避免出现重复解if (i>0 && nums[i] == nums[i-1]){continue;}while(r>l){if ((nums[i]+nums[l]+nums[r]) > 0){r--;}else if((nums[i]+nums[l]+nums[r]) < 0){l++;}else{vector<int> group;group.push_back(nums[i]);group.push_back(nums[l]);group.push_back(nums[r]);result.push_back(group);//去重第三个元素while(r>l && nums[r]==nums[r-1])r--;//去重第二个元素while(r>l && nums[l]==nums[l+1])l++;   r--;l++;}}   }return result;}
};