题目描述

传送门-力扣

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。答案中不可以包含重复的三元组。
示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2] ]

同类型题目

两数之和

思路

排序+双指针
题目中要求找到所有「不重复」且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。因此需要换一种思路来考虑。

  1. 为了保证「不重复」，可以先将原数组进行排序后，再进行三重循环，每次循环都是从上一个循环的后面开始，即保证了我们枚举的三元组(a,b,c)满足a≤b≤c，保证了只有(a,b,c) 这个顺序会被枚举到，而(b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。
  2. 同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复，如[-1,0,1,2,2,2,3]。我们使用三重循环枚举到的第一个三元组为(0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是三元组(0,1,2)，产生了重复。处理这种情况可以先将当前值与前一个值进行比较，如果相同则跳过，直到找到和上个值不同的数。
  3. 采用前两种方法可以保证我们找到的组合是「不重复」的，但是时间复杂度是图片说明 ，可以进行一些优化：可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a + b + c = 0。当第二重循环往后枚举一个元素 b′ 时，由于 b′ > b ，那么满足 a + b′ + c′ = 0 的 c′ 一定有 c′ < c，即 c′ 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。这种方法就是双指针法

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            if(nums[i] > 0) break;

            int left = i + 1, right = nums.size() - 1;
            while(left < right)
            {
                //保证两个指针当前指向的值和上一个值不同
                while(left > i + 1 && left < right && nums[left] == nums[left - 1])
                    left++;
                while(right < nums.size() - 1 && left < right && nums[right] == nums[right + 1])
                    right--;
                if(left >= right)
                    break;
                //两个指针进行位置移动
                if(nums[i] + nums[left] + nums[right] > 0)
                    right--;
                else if(nums[i] + nums[left] + nums[right] < 0)
                    left++;
                else    //保存满足条件的值
                {
                    vector<int> temp = {nums[i], nums[left], nums[right]};
                    res.push_back(temp);
                    left++;
                } 
            }
        }
        return res;
    }
};