LeetCode 15. 3Sum 三数之和

题目链接：点击这里

关键是去掉重复解，map标记超时。

特判，如果数组长度小于 $3$3，返回 $[\ ]$[ ]。

对数组进行排序。

枚举第一位数 $nums[i]$nums[i]，双指针寻找后两位数 $nums[L]$nums[L] 和 $nums[R]$nums[R]

• 若 $nums[i]>0$nums[i]>0：因为已经排好序，所以后面不可能有三个数和等于 $0$0，直接退出。
• 对于重复元素：跳过，避免出现重复解

令左指针 $L=i+1$L=i+1，右指针 $R=n−1$R=n−1，当 $L<R$L<R 时，执行循环：

• 当 $nums[i]+nums[L]+nums[R]==0$nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 $L,R$L,R 移到下一位置，寻找新的解
• 若和大于 $0$0，说明 $nums[R]$nums[R] 太大，$R$R 左移
• 若和小于 $0$0，说明 $nums[L]$nums[L] 太小，$L$L 右移

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] > 0)	break;	//若此处大于0，直接退出
            if(i > 0 && nums[i] == nums[i-1])   continue;	//去重 
            
            int pivot = -nums[i];
            int L = i + 1, R = n - 1;
            
            while(L<R)
            {
                if(nums[L]+nums[R]==pivot)
                {
                    ans.push_back({nums[i],nums[L],nums[R]});
                    ++L;
					--R; 
                    while(L < R && nums[L] == nums[L-1])
                    	++L;
                    while(L < R && nums[R] == nums[R+1])
                    	--R;
                }
                else if(nums[L]+nums[R] < pivot)
                {
                    ++L;
                }
                else
                {
                    --R;
                }
            }
        }
        return ans;
    }
};