LeetCode LCR 007. 三数之和

约 6 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 排序 双指针 LCR

题目描述

✅ LCR 007. 三数之和

image-20260928234718873

题意分析

从整数数组中找出全部和为零的三元组。三个数必须取自不同下标，但它们的数值可以相同；结果按数值组合去重，而不是按下标组合区分。

同一组三个值的不同排列也只算一个答案。需要真正返回全部三元组，若数组不足三个元素或不存在合法组合，返回空结果。

解法：排序后固定一项与双指针

核心思路

[!blue]

先将数组升序排序，使每个三元组都能按非递减顺序表示。然后固定它的第一个位置 i，只在右侧寻找另外两个数，问题就变成有序区间内的两数之和。

令 j = i + 1、k = n - 1。若三数和偏小，当前 j 配上区间最大值仍不够，配更小的右侧数也不可能满足，所以可以右移 j。若和偏大，当前 k 配上区间最小值仍过大，所以可以左移 k。每次都淘汰一批确定无解的配对，不会漏掉答案。

命中时记录三元组，再收缩两端并跳过刚使用过的重复值。对于固定的 nums[i]，某个左值的互补右值已经确定；继续保留相同左值或右值只会得到同样的值组合。数组只是非递减，并非严格递增，因此不能说只移动一端就一定不会再次命中，重复值仍可能命中同一个答案。

外层遇到与上一轮相同的 nums[i] 时也跳过，避免再次枚举同一个首值。这里保留同值的第一次选择，后面仍可取另一位置上的相同数值；不能先对整个数组去重，也不能因为当前值等于后一个值就把当前候选跳过。

当固定值已经大于零时，右侧所有值都不小于它，三数之和不可能再为零，外层可以直接结束。循环始终保持 i < j < k，保证三个下标互异；排序和逐层去重则保证每个值组合只输出一次。

解题步骤

  1. 升序排序，枚举还能给后面留下两个位置的固定下标 i。
  2. 固定值为正时结束；与上一轮首值相同则跳过当前轮。
  3. 在 i 右侧初始化相向双指针，比较三数和。
  4. 和偏小移动 j，偏大移动 k；等于零则保存三元组。
  5. 命中后两端各移动一次，再分别越过刚使用值的重复项，继续寻找不同组合。
  6. 完成所有固定位置后返回结果。

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 排序是全部推理的地基：既统一了三元组内部顺序，又提供了单调性。
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();
        int n = nums.length;

        // nums[i] 是三元组里最小的数，一旦为正后面必然无解。
        for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
            // 与前一个值相同则跳过，避免以同一个最小值重复搜索。
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int j = i + 1;
            int k = n - 1;

            while (j < k) {
                int x = nums[i] + nums[j] + nums[k];

                if (x < 0) {
                    ++j;
                } else if (x > 0) {
                    --k;
                } else {
                    answer.add(List.of(nums[i], nums[j++], nums[k--]));

                    // 跳过与刚用过的值相同的元素，两侧都要跳。
                    while (j < k && nums[j] == nums[j - 1]) {
                        ++j;
                    }

                    while (j < k && nums[k] == nums[k + 1]) {
                        --k;
                    }
                }
            }
        }

        return answer;
    }
}

import (
    "sort"
)

func threeSum(nums []int) (answer [][]int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i < n-2 && nums[i] <= 0; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        j, k := i+1, n-1
        for j < k {
            x := nums[i] + nums[j] + nums[k]
            if x < 0 {
                j++
            } else if x > 0 {
                k--
            } else {
                answer = append(answer, []int{
                    nums[i],
                    nums[j],
                    nums[k],
                })
                j, k = j+1, k-1
                for j < k && nums[j] == nums[j-1] {
                    j++
                }
                for j < k && nums[k] == nums[k+1] {
                    k--
                }
            }
        }
    }
    return
}

复杂度分析

设数组长度为 $n$，答案三元组数量为 $r$。

  • 时间复杂度：$O(n^2)$。排序需要 $O(n\log(n+1))$，每个固定位置的双指针只进行一次线性收缩。
  • 辅助空间复杂度：双指针部分为 $O(1)$，整体额外空间取决于排序实现；返回结果另占 $O(r)$，最坏可达平方级。

关键点总结

[!green]

  • 排序同时提供端点移动的单调依据和唯一的三元组内部顺序。
  • 固定首值后，剩余问题是有序两数之和。
  • 同一枚举层跳过重复值，不等于删除输入中的重复元素。
  • 首值为正即可停止，严格下标顺序自然排除复用同一位置。

易错点总结

[!yellow]

  • 外层与前一个已处理值比较去重，不要因等于后一个值就跳过，后者可能漏掉需要两个同值的答案。
  • 命中后需要推进指针，随后越过重复值，避免再次输出相同三元组。
  • 指针比较使用 j < k，相遇时不能把同一下标作为两个数。
  • 原数组未排序时，不能根据和的大小直接移动两端。
  • 结果按值去重，但每个值仍需要一个实际位置，不能通过预先删除重复元素简化输入。

相似题目

题目 难度 关联与区别
16. 最接近的三数之和 中等 同样排序后固定一项并对撞指针，原题找最接近的和，本题输出恰好为0的全部不重复组合。
18. 四数之和 中等 把固定一个数扩展为固定两个数，内层仍复用双指针和重复值处理。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/15415725
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！