15.三数之和

问题

传送门：https://leetcode.cn/problems/3sum/description/

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路

不妨以[-1,0,1,2,-1,-4]为例思考如何找到三元组。

• i=0，nums[i]=-1，则nums[j]+nums[k]=1，转化为在剩余的数组元素中的两数之和为1的问题。
• i=1，nums[i]=0，则nums[j]+nums[k]=0，转化为在剩余的数组元素中的两数之和为0的问题。
• ……

而两数之和问题可以使用双指针解决，将数组按照非递减排序后，设置头指针和尾指针分别指向数组头部和尾部：

• 两指针所指的数之和大于target，则左移右指针；
• 两指针所指的数之和小于target，则右移左指针；
• 两指针所指的数之和大于target，找到答案。

关键

此题的关键在于，去除重复解。其实设置了三个指针，每次移动指针时，如果当前指针所指和上一次所指的元素相同时，继续将指针往右移，即可保证选中的解均不重复。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> cnt;
        int i = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        while(i < n) {
            while(i && i < n && nums[i] == nums[i-1])   i++;
            int l = i+1, r = n-1;
            while(l < r) {
                int tgt = -nums[i];
                if(nums[l] + nums[r] > tgt) r--;
                else if(nums[l] + nums[r] < tgt)    l++;
                else {
                    // 选中[nums[i], nums[l], nums[r]]
                    vector<int> temp = {nums[i], nums[l], nums[r]};
                    cnt.push_back(temp);
                    l++, r--;
                    // 去重：此时i不变，考虑左指针l、右指针r指向元素的重复性
                    // e.g. [-3, 0, 1, 1, 1, 2, 2, 2, 2]
                    while(l < r && nums[l] == nums[l-1])    l++; // 注意nums[l-1]已经选过
                    while(l < r && nums[r] == nums[r+1])    r--; // 注意nums[r+1]已经选过
                }
            }
            i++;
        }
        return cnt;
    }
};