京公网安备11010502063487号给定一个整数数组，找出所有和为 0 的三元组，结果里不能有重复的三元组（顺序无所谓）。暴力做法是三层循环加去重，时间 O(n³)。标准做法是先排序，然后固定第一个数，在它右边用双指针找另外两个数，时间降到 O(n²)。这道题真正的难点在于去重：数组里有很多重复值时，同一个三元组会被反复找到。本文实测暴力解和双指针的耗时差距，展示不去重会得到什么，给出五种语言的实现，并把双指针和去重的过程做成分步演示。
完整题目见官方页面（链接在文末）。这道题的答案是一个集合，三元组之间的顺序、三元组内部的顺序都不作要求，所以核对时先把每个三元组内部排序，再把所有三元组排序后比较。基准解是三层循环枚举，用集合去重。一共 12 组用例，覆盖：官方示例、空数组和单元素、全是 0、正负数各半、大量重复值：
输入 [[-1,0,1,2,-1,-4]] 输出 [[-1,-1,2],[-1,0,1]] 输入 [[0,1,1]] 输出 [] 输入 [[0,0,0]] 输出 [[0,0,0]] 输入 [[0,0,0,0]] 输出 [[0,0,0]] 输入 [[]] 输出 [] 输入 [[1]] 输出 []
先排序再双指针本身不难，但如果找到一个三元组之后只是把 l 和 r 各移动一格，就会重复找到相同的三元组：因为数组里有相同的值。下面是没有任何去重的写法，与正确写法的真实结果：
# 有序 + 双指针，但没有跳过重复值的写法
[-1, 0, 1, 2, -1, -4]: 不去重 -> [[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]
solve -> [[-1, -1, 2], [-1, 0, 1]]
[0, 0, 0, 0, 0, 0]: 不去重 -> [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
solve -> [[0, 0, 0]]
[-2, 0, 0, 2, 2]: 不去重 -> [[-2, 0, 2], [-2, 0, 2]]
solve -> [[-2, 0, 2]]官方示例 [-1, 0, 1, 2, -1, -4] 里有两个 -1，不去重的写法把 [-1, 0, 1] 找到了两次；六个 0 的数组，不去重的写法返回了六个一模一样的 [0, 0, 0]，而题目要求值相同的三元组只算一个；[-2, 0, 0, 2, 2] 里 [-2, 0, 2] 被找到两次。去重要做三处：固定的第一个数与前一个相同就跳过；找到答案后，跳过与刚用过的第二个数相同的值；同时跳过与刚用过的第三个数相同的值。
先排序。对每个 i，在 [i+1, n-1] 上放两个指针 l、r：三数之和小于 0 就让 l 右移，大于 0 就让 r 左移，等于 0 就记录答案并做上述去重。还有一个剪枝：nums[i] > 0 时，后面的数只会更大，不可能凑出 0，可以直接结束。Python、Java、Go、JavaScript、C++ 五种语言都是真实编译运行的；Go 需要 sort 包，其他语言用内置的排序。
Python · 解法代码def solve(nums): nums.sort() res = [] n = len(nums) for i in range(n - 2): if nums[i] > 0: # 最小的数都大于 0，后面不可能凑出 0 break if i > 0 and nums[i] == nums[i - 1]: # 相同的第一个数只处理一次，避免重复三元组 continue l, r = i + 1, n - 1 while l < r: s = nums[i] + nums[l] + nums[r] if s < 0: l += 1 elif s > 0: r -= 1 else: res.append([nums[i], nums[l], nums[r]]) l += 1 r -= 1 while l < r and nums[l] == nums[l - 1]: # 跳过相同的第二个数 l += 1 while l < r and nums[r] == nums[r + 1]: # 跳过相同的第三个数 r -= 1 return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[-1,0,1,2,-1,-4]] → [[-1,-1,2],[-1,0,1]] [[0,1,1]] → [] [[0,0,0]] → [[0,0,0]] [[0,0,0,0]] → [[0,0,0]] [[]] → [] [[1]] → []
Java · 解法代码class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 2; i++) { if (nums[i] > 0) break; // 最小的数都大于 0，不可能凑出 0 if (i > 0 && nums[i] == nums[i - 1]) continue; // 相同的第一个数只处理一次 int l = i + 1, r = n - 1; while (l < r) { int s = nums[i] + nums[l] + nums[r]; if (s < 0) l++; else if (s > 0) r--; else { res.add(Arrays.asList(nums[i], nums[l], nums[r])); l++; r--; while (l < r && nums[l] == nums[l - 1]) l++; // 跳过相同的第二个数 while (l < r && nums[r] == nums[r + 1]) r--; // 跳过相同的第三个数 } } } return res; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[-1,0,1,2,-1,-4]] → [[-1,-1,2],[-1,0,1]] [[0,1,1]] → [] [[0,0,0]] → [[0,0,0]] [[0,0,0,0]] → [[0,0,0]] [[]] → [] [[1]] → []
Go · 解法代码import "sort" func threeSum(nums []int) [][]int { sort.Ints(nums) res := [][]int{} n := len(nums) for i := 0; i < n-2; i++ { if nums[i] > 0 { // 最小的数都大于 0，不可能凑出 0 break } if i > 0 && nums[i] == nums[i-1] { // 相同的第一个数只处理一次 continue } l, r := i+1, n-1 for l < r { s := nums[i] + nums[l] + nums[r] if s < 0 { l++ } else if s > 0 { r-- } else { res = append(res, []int{nums[i], nums[l], nums[r]}) l++ r-- for l < r && nums[l] == nums[l-1] { // 跳过相同的第二个数 l++ } for l < r && nums[r] == nums[r+1] { // 跳过相同的第三个数 r-- } } } } return res }
$ go build -o bin . && ./bin < cases.jsonl [[-1,0,1,2,-1,-4]] → [[-1,-1,2],[-1,0,1]] [[0,1,1]] → [] [[0,0,0]] → [[0,0,0]] [[0,0,0,0]] → [[0,0,0]] [[]] → [] [[1]] → []
JavaScript · 解法代码function threeSum(nums) { nums.sort((a, b) => a - b); const res = []; const n = nums.length; for (let i = 0; i < n - 2; i++) { if (nums[i] > 0) break; // 最小的数都大于 0，不可能凑出 0 if (i > 0 && nums[i] === nums[i - 1]) continue; // 相同的第一个数只处理一次 let l = i + 1, r = n - 1; while (l < r) { const s = nums[i] + nums[l] + nums[r]; if (s < 0) l++; else if (s > 0) r--; else { res.push([nums[i], nums[l], nums[r]]); l++; r--; while (l < r && nums[l] === nums[l - 1]) l++; // 跳过相同的第二个数 while (l < r && nums[r] === nums[r + 1]) r--; // 跳过相同的第三个数 } } } return res; }
$ node run.js < cases.jsonl [[-1,0,1,2,-1,-4]] → [[-1,-1,2],[-1,0,1]] [[0,1,1]] → [] [[0,0,0]] → [[0,0,0]] [[0,0,0,0]] → [[0,0,0]] [[]] → [] [[1]] → []
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = nums.size(); for (int i = 0; i < n - 2; i++) { if (nums[i] > 0) break; // 最小的数都大于 0，不可能凑出 0 if (i > 0 && nums[i] == nums[i - 1]) continue; // 相同的第一个数只处理一次 int l = i + 1, r = n - 1; while (l < r) { int s = nums[i] + nums[l] + nums[r]; if (s < 0) l++; else if (s > 0) r--; else { res.push_back({nums[i], nums[l], nums[r]}); l++; r--; while (l < r && nums[l] == nums[l - 1]) l++; // 跳过相同的第二个数 while (l < r && nums[r] == nums[r + 1]) r--; // 跳过相同的第三个数 } } } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[-1,0,1,2,-1,-4]] → [[-1,-1,2],[-1,0,1]] [[0,1,1]] → [] [[0,0,0]] → [[0,0,0]] [[0,0,0,0]] → [[0,0,0]] [[]] → [] [[1]] → []
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
用一个取值在 -1000 到 1000 之间的伪随机数组，每个规模取三次中最快的一次：
数组长度 n | 暴力解 | 本文解法
100 | 4.865 ms | 0.170 ms
300 | 137.732 ms | 1.414 ms
1000 | （未测，太慢） | 24.961 ms
3000 | （未测，太慢） | 162.852 ms暴力解从 100 到 300（3 倍）耗时从 4.7ms 涨到 140.5ms，增长约 30 倍，接近立方（27 倍），所以更大的规模没有再测。双指针解法从 100 到 300 增长约 8.7 倍，接近平方（9 倍）；从 300 到 1000 增长约 17 倍（3.3 倍规模，平方是 11 倍），从 1000 到 3000 增长约 6.5 倍（平方是 9 倍），中间几档有偏差，我没有细究原因（可能与数据规模变化导致的缓存和排序开销占比变化有关，这只是猜测），整体上是平方级增长。
Python 版本另外和暴力解做了随机对拍：
随机对拍 10000 组（长度 0 到 14、取值 -6 到 6 的随机数组（重复值很多，是去重逻辑最容易出错的情形）；比较时不区分三元组的先后和内部顺序），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，其中包含大量重复值的输入，没有做大规模随机对拍。
下面的演示用官方示例 [-1, 0, 1, 2, -1, -4]，排序后是 [-4, -1, -1, 0, 1, 2]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的三元组集合与 solve 的返回值一致。注意 i = 2 时，nums[2] 与前一个相同，被整个跳过（淡色）。