0015. 三数之和

[giscus[bot]]

0015. 三数之和

https://algo.itcharge.cn/solutions/0001-0099/3sum/

[Therm4l]

参考c++代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n - 2; i++){
            if(i && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = n - 1;
            while(j < k){
                int s = nums[i] + nums[j] + nums[k];
                if(s > 0) k--;
                else if(s < 0) j++;
                else{
                    res.push_back({nums[i], nums[j], nums[k]});
                    for (++j; j < k && nums[j] == nums[j - 1]; ++j);
                    for (--k; k > j && nums[k] == nums[k + 1]; --k);
                }
            }
        }
        return res;
    }
};

[youpingfang]

为什么 “非 0 时不需要专门跳过重复”？
当 total != 0 时（即和小于 0 或大于 0），我们需要通过移动指针（left += 1 或 right -= 1）来调整总和：
此时即使遇到重复元素，指针的移动会自然跳过它们（例如，若 nums[left] 和 nums[left+1] 相等，移动 left 后会直接指向 left+1，无需额外处理）。
更重要的是：非 0 的情况下，重复元素不会产生重复的有效解（因为总和不满足条件），所以无需专门处理。

def three_sum(nums):
    # 排序数组，为后续去重和双指针操作做准备
    nums.sort()
    n = len(nums)
    result = []
    
    # 遍历每个可能的第一个元素
    for i in range(n - 2):
        # 跳过重复的第一个元素
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # 双指针初始化
        left = i + 1
        right = n - 1
        
        # 移动双指针寻找满足条件的三元组
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                # 找到符合条件的三元组，添加到结果
                result.append([nums[i], nums[left], nums[right]])
                
                # 跳过重复的第二个元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # 跳过重复的第三个元素
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                # 移动双指针继续寻找
                left += 1
                right -= 1
            elif total < 0:
                # 和小于0，需要增大，移动左指针
                left += 1
            else:
                # 和大于0，需要减小，移动右指针
                right -= 1
    
    return result