15. 三数之和

题目描述

给你一个数组，任选3个数，其和等于0。返回全部的这3个数。不能包含一样的3元组。

解题思路

本题也是枚举，不过是如何快速的进行枚举。

要快速就要想到哈希或者二分。

先固定一个数，然后枚举另外2个数即可。为了实现双指针，就要先进行排序。

双指针：

left+right大于sum ，right到中间
小于sum，left到中间。
等于就是结果。是结果也不能跳出循环，因为和等于sum，会有多个。（这里也要进行去重的操作）

因为不能包含一样的，所以在固定数的时候，如果下一个与当前值相同就可以跳过。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int sum=-nums[i];
            
            int left=i+1,right=n-1;
            //双指针
            while(left<right)
            {
                if(nums[left]+nums[right]>sum) right--;
                else if(nums[left]+nums[right]<sum) left++;
                else
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    //去重
                    while(left+1<n&&nums[left]==nums[left+1]) left++;
                    while(right-1>=0&&nums[right]==nums[right-1]) right--;

                    left++,right--;
                }
            }
            //固定一个数的去重
            while(i+1<n&&nums[i]==nums[i+1]) i++;
        }
        return ret;
    }
};