力扣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;
    }
};