LeetCode 题解
    15. 3Sum

    15. 3Sum

    题目描述：给定一个数组，寻找所有不重复的三元组使得它们的和为0

    核心思想

    3sum 的思想其实跟 2sum 的思想非常类似，都是利用双指针的技巧来解题，区别在于需要进行去重，已经排好序的数组去重其实只要不停地滑动到与前一个元素不同即可

    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    if (nums.size() < 3) return res;
	// 先排序
    sort(nums.begin(), nums.end());
    for(int i=0;i<nums.size()-2&&nums[i]<=0;++i) {
        int start=i+1;
        int end=nums.size()-1;
		// 双指针
        while(start<end) {
            int sum = nums[i]+nums[start]+nums[end];
            if (sum<0) ++start;
            else if(sum>0) --end;
            else {
                vector<int> v(3);
                v[0]=nums[i];
                v[1]=nums[start];
                v[2]=nums[end];
                res.push_back(v);
				// 找到一组之后双指针要滑动去重
                do {
                    ++start;
                } while(start<end && nums[start-1]==nums[start]);
                do {
                    --end;
                } while(start<end && nums[end+1]==nums[end]);
            }
        }
		// 选择的第一个数也需要去重
        while(i<nums.size()-2 && nums[i+1]==nums[i]) ++i;
    }
    return res;
}

    收获

    双指针滑动去重，同样 4sum 的思路也是一模一样，先选择两个数，然后再用双指针找四个和为定值的下标，也是一样的去重思想

    #双指针

    1409. Queries on a Permutation With Key152. Maximum Product Subarray