题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 思路2: 排序后用双指针来查找另外两个数字
        vector<vector<int>> result;
        sort(nums.begin() , nums.end());

        // 枚举所有三元组的左端点
        for(int i = 0 ; i < nums.size() ; i ++)
        {
            // 每当查找一个数时,会查找出所有的可能性,那么不需要重复查找相邻的数字
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            if(nums[i] > 0) break;
            int target = -nums[i];
            int l = i + 1 , r = nums.size() - 1;

            while(l < r)
            {
                int sum = nums[l] + nums[r];
                if(sum == target)
                {
                    result.push_back({nums[i] , nums[l] , nums[r]});

                    // 跳过查找中相同的数字
                    while(l < r && nums[l] == nums[l+1]) l ++;
                    while(l < r && nums[r] == nums[r-1]) r --;

                    l ++;
                    r --;
                } // 这里会不会漏解 不会漏解 因为每次都在排除不可能解
                // 当 移动一个端点时 意味着该端点和另一次任意数字的组合都不可能是解
                else if(sum > target) {
                    r --;
                } else {
                    l ++;
                }
            }
        }
        return result;
    }
};