leetcode 15. 三数之和

15. 三数之和

给你一个整数数组 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) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end()); //使用双指针前要先排序
        for(int i = 0; i < nums.size() - 2; ++i) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            // 避免重复的第一个元素
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1; 
            int right = nums.size() - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if(sum > 0) {
                    right--;
                }
                else if(sum < 0){
                    left++;
                }
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    
                    // 避免重复的第二个元素
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 避免重复的第三个元素
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 找到答案时，双指针同时收缩
                    left++;
                    right--;
                }
            }            
        }
        return result;
    }
};

#

a的去重

说到去重，其实主要考虑三个数的去重。a, b ,c,对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断nums[i]与 nums[i + 1]是否相同，还是判断 nums[i] 与nums[i-1]是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是 这样：

if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

这是一个非常细节的思考过程。

b与c的去重

很多同学写本题的时候，去重的逻辑多加了 对right 和left 的去重：（代码中注释部分）

while (right > left) {
    if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }
}

但细想一下，这种去重其实对提升程序运行效率是没有帮助的。

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right-- 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right--; 这一行代码，其实就是把需要执行的逻辑提前执行了，但并没有减少 判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已。

while (right > left) {
	// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
	/*
	while (right > left && nums[right] == nums[right - 1]) right--;
	while (right > left && nums[left] == nums[left + 1]) left++;
	*/
	if (nums[i] + nums[left] + nums[right] > 0) right--;
	...
}

方法二: 哈希表(思想)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        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; // 避免重复的第一个元素
            }

            unordered_set<int> seen; // 用于记录已经遍历过的元素
            for (int j = i + 1; j < nums.size(); ++j) {
                int c = 0 - (nums[i] + nums[j]);
                if (seen.count(c)) {
                    result.push_back({nums[i], c, nums[j]});
                    while (j + 1 < nums.size() && nums[j] == nums[j + 1]) {
                        ++j; // 跳过重复的第二个元素
                    }
                }
                seen.insert(nums[j]);
            }
        }

        return result;
    }
};