三数之和 - Stellar Observer Protocol

675 字

3 分钟

三数之和

2025-08-22

无标签

题目描述#

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

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

解题思路#

排序预处理：
- 将数组升序排序，便于双指针操作
- 时间复杂度 O(n log n)
固定指针遍历：
- 外层循环固定第一个数 nums[i]
- 内层使用双指针寻找另外两数
双指针搜索：
- 左指针 left = i + 1
- 右指针 right = n - 1
和值判断：
- 三数和 > 0：右指针左移
- 三数和 < 0：左指针右移
- 三数和 = 0：记录结果并移动双指针
去重处理：
- 跳过重复的 nums[i]
- 双指针移动时跳过相同值

关键洞察#

排序必要性：
- 排序后双指针能高效搜索目标值
- 避免 O(n³) 的暴力解法
双指针优势：
- 将两数之和优化为 O(n) 操作
- 总体复杂度降至 O(n²)
去重策略：
- 固定指针和前值比较避免重复
- 双指针跳过相同元素防止重复组合
剪枝优化：
- nums[i] > 0 时提前终止
- 最小三数和 > 0 时结束搜索

复杂度分析#

指标	说明
时间复杂度	O(n²)：排序 O(n log n) + 双指针 O(n²)
空间复杂度	O(1) 或 O(n)：取决于排序实现
最优情况	O(n²)：无法低于平方复杂度

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @return {number[][]}
4
 */
5
var threeSum = function (nums) {
6
    const result = [];
7
    nums.sort((a, b) => a - b);
8

9
    for (let i = 0; i < nums.length - 2; i++) {
10
        if (i > 0 && nums[i] === nums[i - 1]) continue;
11
        if (nums[i] > 0) break; // No need to continue if the smallest is > 0
12

13
        let l = i + 1, r = nums.length - 1;
14
        while (l < r) {
15
            const sum = nums[i] + nums[l] + nums[r];
16
            if (sum === 0) {
17
                result.push([nums[i], nums[l], nums[r]]);
18
                while (l < r && nums[l] === nums[l + 1]) l++;
19
                while (l < r && nums[r] === nums[r - 1]) r--;
20
                l++;
21
                r--;
22
            } else if (sum < 0) {
23
                l++;
24
            } else {
25
                r--;
26
            }
27
        }
28
    }
29

30
    return result;
31
};