Day10-三数之和

🔗 LeetCode 15 - 三数之和

📌 题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]，满足：

i ≠ j、i ≠ k 且 j ≠ k
nums[i] + nums[j] + nums[k] == 0

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

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

---

💡 解题思路

1. 先将数组排序；
2. 固定一个数 nums[i]，再用双指针在 i+1...n-1 范围内找两个数的和为 -nums[i]；
3. 注意跳过重复数字以避免重复结果。

时间复杂度为 O(n^2)。

---

✅ JavaScript 实现

var threeSum = function(nums) {
    nums.sort(function(a, b) { return a - b; });
    let res = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                res.push([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--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
};

---

🟣 Swift 实现

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let nums = nums.sorted()
        var res = [[Int]]()

        for i in 0..<nums.count {
            if i > 0 && nums[i] == nums[i - 1] { continue }

            var left = i + 1
            var right = nums.count - 1

            while left < right {
                let sum = nums[i] + nums[left] + nums[right]
                if sum == 0 {
                    res.append([nums[i], nums[left], nums[right]])
                    while left < right && nums[left] == nums[left + 1] { left += 1 }
                    while left < right && nums[right] == nums[right - 1] { right -= 1 }
                    left += 1
                    right -= 1
                } else if sum < 0 {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        return res
    }
}