京公网安备11010502063487号给定一个整数数组和目标值 target，找出所有和为 target 的不重复四元组。做法是三数之和的延伸：排序后用两层循环固定前两个数，再在右侧用双指针找后两个数，时间 O(n³)。这道题相比三数之和多了一个真实的陷阱：数组元素和 target 的范围都到 10 亿，四个数相加可能超过 32 位整数的范围。本文用真实的 Java 和 C++ 程序展示溢出，实测暴力解和双指针的耗时，给出五种语言的实现，并把两层循环加双指针的过程做成分步演示。
完整题目见官方页面（链接在文末）。答案是四元组的集合，四元组之间、四元组内部的顺序都不作要求，核对时先把每个四元组内部排序，再整体排序后比较。基准解是四层循环加集合去重。一共 12 组用例，覆盖：官方示例、四个相同的数、数组不足四个数、空数组、以及几组接近 32 位整数边界的大数：
输入 [[1,0,-1,0,-2,2],0] 输出 [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 输入 [[2,2,2,2,2],8] 输出 [[2,2,2,2]] 输入 [[0,0,0,0],0] 输出 [[0,0,0,0]] 输入 [[1,2,3],6] 输出 [] 输入 [[],0] 输出 [] 输入 [[1000000000,1000000000,1000000000,1000000000],-294967296] 输出 []
32 位有符号整数的最大值约为 21.47 亿，四个 10 亿相加是 40 亿，已经超出范围。用 int 存和的话，结果会回绕成另一个数，有可能恰好等于 target，把根本不成立的四元组当成答案。下面是真实的 Java 和 C++ 程序：四个 1000000000，target 取 -294967296（这是 40 亿回绕之后的值）：
四个 1000000000，target = -294967296（真实的和是 4000000000）： Java int 求和 = -294967296，等于 target？ true Java long 求和 = 4000000000，等于 target？ false C++ int 求和 = -294967296，等于 target？ true C++ long long 求和 = 4000000000，等于 target？ false 本文的 solve（Python，整数不会溢出）-> []
Java 和 C++ 里用 int 求和得到 -294967296，与 target 相等，错误地认为这四个数是一个解；改成 long / long long 之后得到真实的 4000000000，与 target 不等，答案应当是空。用例里专门放了这两组数据（以及它们的对称情形），Java 和 C++ 的实现里所有求和都先转成 64 位再比较，Go 的 int 在 64 位平台上是 64 位，JavaScript 的数字是双精度浮点，40 亿以内都是精确的，Python 的整数不会溢出，所以这三种语言不需要特殊处理。五种语言在这些用例上都与基准结果一致。这个实验只在我这台 64 位机器上做；在 int 只有 32 位的 Go 平台（例如 32 位系统）上，需要同样处理，我没有实际测过。
先排序。第一层循环固定 nums[i]，第二层固定 nums[j]，在 [j+1, n-1] 上放 l、r，逻辑与三数之和一样。去重要做四处：i、j 遇到与前一个相同的值就跳过，l、r 命中后跳过相同的值。另外做了两处剪枝：如果以当前 i 开头的最小四数和已经大于 target，之后的 i 只会更大，直接结束；如果以当前 i 开头的最大四数和还小于 target，这个 i 不可能成功，换下一个。第二层循环同理。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums, target): nums.sort() n = len(nums) res = [] for i in range(n - 3): if i > 0 and nums[i] == nums[i - 1]: # 第一个数去重 continue if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target: # 最小的四数和都超了，后面更大 break if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target: # 最大的四数和都不够，换下一个 i continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j - 1]: # 第二个数去重 continue if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target: break if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target: continue l, r = j + 1, n - 1 while l < r: s = nums[i] + nums[j] + nums[l] + nums[r] if s < target: l += 1 elif s > target: r -= 1 else: res.append([nums[i], nums[j], 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,0,-2,2],0] → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] [[2,2,2,2,2],8] → [[2,2,2,2]] [[0,0,0,0],0] → [[0,0,0,0]] [[1,2,3],6] → [] [[],0] → [] [[1000000000,1000000000,1000000000,1000000000],-294967296] → []
Java · 解法代码class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // 第一个数去重 if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // 最小四数和已超，后面更大 if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; // 最大四数和不够 for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 第二个数去重 if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue; int l = j + 1, r = n - 1; while (l < r) { long s = (long) nums[i] + nums[j] + nums[l] + nums[r]; // 用 long，避免 int 溢出 if (s < target) l++; else if (s > target) r--; else { res.add(Arrays.asList(nums[i], nums[j], 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,0,-2,2],0] → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] [[2,2,2,2,2],8] → [[2,2,2,2]] [[0,0,0,0],0] → [[0,0,0,0]] [[1,2,3],6] → [] [[],0] → [] [[1000000000,1000000000,1000000000,1000000000],-294967296] → []
Go · 解法代码import "sort" func fourSum(nums []int, target int) [][]int { sort.Ints(nums) n := len(nums) res := [][]int{} for i := 0; i < n-3; i++ { if i > 0 && nums[i] == nums[i-1] { // 第一个数去重 continue } if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target { // 最小四数和已超，后面更大 break } if nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target { // 最大四数和不够 continue } for j := i + 1; j < n-2; j++ { if j > i+1 && nums[j] == nums[j-1] { // 第二个数去重 continue } if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target { break } if nums[i]+nums[j]+nums[n-2]+nums[n-1] < target { continue } l, r := j+1, n-1 for l < r { s := nums[i] + nums[j] + nums[l] + nums[r] // Go 的 int 是 64 位，不会溢出 if s < target { l++ } else if s > target { r-- } else { res = append(res, []int{nums[i], nums[j], 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,0,-2,2],0] → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] [[2,2,2,2,2],8] → [[2,2,2,2]] [[0,0,0,0],0] → [[0,0,0,0]] [[1,2,3],6] → [] [[],0] → [] [[1000000000,1000000000,1000000000,1000000000],-294967296] → []
JavaScript · 解法代码function fourSum(nums, target) { nums.sort((a, b) => a - b); const n = nums.length; const res = []; for (let i = 0; i < n - 3; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; // 第一个数去重 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // 最小四数和已超，后面更大 if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; // 最大四数和不够 for (let j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] === nums[j - 1]) continue; // 第二个数去重 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue; let l = j + 1, r = n - 1; while (l < r) { const s = nums[i] + nums[j] + nums[l] + nums[r]; // JS 数字是双精度，4e9 内精确 if (s < target) l++; else if (s > target) r--; else { res.push([nums[i], nums[j], 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,0,-2,2],0] → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] [[2,2,2,2,2],8] → [[2,2,2,2]] [[0,0,0,0],0] → [[0,0,0,0]] [[1,2,3],6] → [] [[],0] → [] [[1000000000,1000000000,1000000000,1000000000],-294967296] → []
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int n = nums.size(); vector<vector<int>> res; for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // 第一个数去重 if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // 最小四数和已超，后面更大 if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 第二个数去重 if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue; int l = j + 1, r = n - 1; while (l < r) { long long s = (long long)nums[i] + nums[j] + nums[l] + nums[r]; // 用 long long，避免 int 溢出 if (s < target) l++; else if (s > target) r--; else { res.push_back({nums[i], nums[j], 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,0,-2,2],0] → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] [[2,2,2,2,2],8] → [[2,2,2,2]] [[0,0,0,0],0] → [[0,0,0,0]] [[1,2,3],6] → [] [[],0] → [] [[1000000000,1000000000,1000000000,1000000000],-294967296] → []
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
数据是伪随机的偶数，target 取奇数 1，每个规模取三次中最快的一次：
数组长度 n | 暴力解 | 本文解法
50 | 9.423 ms | 0.621 ms
100 | 154.962 ms | 5.192 ms
200 | （未测，太慢） | 41.030 ms
400 | （未测，太慢） | 371.496 ms暴力解从 50 到 100（2 倍）耗时增长约 16 倍，正好是四次方（2 的 4 次方等于 16），所以更大规模没有再测。双指针解法在 50、100、200、400 上的耗时依次是 0.6ms、5.2ms、41ms、371ms，每翻一倍增长约 8 到 9 倍，符合三次方（8 倍）。这里的剪枝在这批数据上作用有限，最坏情形仍是 O(n³)。
Python 版本另外和暴力解做了随机对拍：
随机对拍 5000 组（长度 0 到 11、取值 -5 到 5 的随机数组（重复值很多），target 取 -8 到 8；比较时不区分四元组的先后和内部顺序），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1, 0, -1, 0, -2, 2]，target = 0，排序后是 [-2, -1, 0, 0, 1, 2]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的四元组集合与 solve 的返回值一致。注意跳过重复值（淡色）和最后 i = 2 时剪枝直接结束的那一帧。