算法刷题系列（十三）：N 数之和——排序、双指针与去重
算法刷题系列（十三）：N 数之和——排序、双指针与去重
前面的哈希表篇用“当前值需要哪个配对值”解决两数之和；双指针篇则说明了如何利用有序数组从两端缩小候选。本篇把两种思路连起来：先排序，再固定若干个数，最后用双指针寻找剩余目标。
我们从原创的三数之和例子开始，逐步推广到一般 k 数之和，重点处理三个容易出错的问题：排序后的剪枝、重复组合去重，以及递归中的数值溢出。代码提供 Java 与 Python 两个版本。
一、题目：找出所有不重复的三元组
给定整数数组 nums 和目标值 target，找出所有满足下面条件的三元组：
1
2
nums[i] + nums[j] + nums[k] = target
i < j < k
返回的三元组不能重复，但原数组中的重复数值可以使用，只要来自不同下标。
例如：
1
2
nums = [-4, -1, -1, 0, 2, 5]
target = 0
不重复的数值组合为：
1
2
[-4, -1, 5]
[-1, -1, 2]
二、从暴力枚举到排序加双指针
直接枚举三个下标，需要三层循环，时间复杂度为 O(n³)。如果先固定一个下标 i，剩下的问题是：
1
在 i 之后找两个数，使它们的和等于 target - nums[i]
把数组排序后，剩余两数可以用相向双指针在线性时间内查找。整体流程是：
- 对数组排序。
- 依次固定第一个数
nums[i]。 - 在右侧区间设置
left = i + 1、right = n - 1。 - 比较三数之和与目标值，按排序性质移动指针。
- 找到答案后跳过相同数值，避免返回重复三元组。
排序耗时 O(n log n)，外层固定一个数，内层双指针扫描，因此总时间复杂度为 O(n²)。
三、手动推演
排序后数组为：
1
[-4, -1, -1, 0, 2, 5]
固定 -4，剩余目标为 4：
| 固定值 | 左值 | 右值 | 总和 | 操作 |
|---|---|---|---|---|
| -4 | -1 | 5 | 0 | 命中 [-4, -1, 5]，两端向内移动 |
固定第一个 -1 后，剩余目标为 1：
| 固定值 | 左值 | 右值 | 总和 | 操作 |
|---|---|---|---|---|
| -1 | 第二个 -1 | 5 | 3 | 总和大，右指针左移 |
| -1 | 第二个 -1 | 2 | 0 | 命中 [-1, -1, 2] |
两组答案分别是：
1
2
-4 + -1 + 5 = 0
-1 + -1 + 2 = 0
推演时要始终把固定值计入总和；对每个固定值，双指针只负责寻找其余 k - 1 个数的目标和。
四、为什么需要去重？
数组中可能有重复值。如果每次只移动一个位置，算法可能多次得到相同的数值组合。
需要区分两种重复：
1. 固定位置重复
当外层固定 nums[i] 后，如果 nums[i] == nums[i - 1]，那么前一个位置已经搜索过相同固定值的所有组合。当前轮会产生重复结果，可以跳过。
代码条件：
1
i > start 且 nums[i] == nums[i - 1] 时跳过
这里必须要求 i > start。若从当前递归层的起点开始就跳过相同值，会错误地忽略合法的重复元素组合，例如 [-1, -1, 2]。
2. 双指针命中后的重复值
找到一个组合后，左右指针都向中间移动，并分别跳过与刚使用值相同的元素。这样不会重复输出同一组数值。
去重只影响结果集合，不改变“值来自不同下标”的要求：左右指针始终位于固定下标之后，且 left < right。
五、剪枝：提前停止无望的搜索
排序后的数组允许使用最小值和最大值判断当前固定选择是否可能完成。
假设还要选 k 个数，当前固定位置为 start，当前目标为 target：
- 若从最小的
k个可选数相加仍大于target，当前以及后续更大的固定值都不可能找到答案，可以结束本层循环。 - 若当前固定值加上最大的
k - 1个可选数仍小于target，当前固定值太小，但后续固定值可能更大，所以可以跳过当前值，继续下一轮。
对三数之和，条件可写成：
1
2
nums[i] + nums[i + 1] + nums[i + 2] > target → break
nums[i] + nums[n - 2] + nums[n - 1] < target → continue
加法比较可能溢出，因此实现中使用更宽整数类型。
六、Java 实现：通用 k 数之和
下面的实现返回所有不重复的值组合。输入会复制后排序，不会修改调用者传入的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class KSum {
public static List<List<Long>> kSum(
int[] values, int k, long target) {
if (values == null) {
throw new IllegalArgumentException("values must not be null");
}
if (k < 2) {
throw new IllegalArgumentException("k must be at least 2");
}
int[] sorted = values.clone();
Arrays.sort(sorted);
return search(sorted, 0, k, target);
}
private static List<List<Long>> search(
int[] values, int start, int k, long target) {
List<List<Long>> result = new ArrayList<>();
int n = values.length;
if (n - start < k) {
return result;
}
long minimum = 0;
long maximum = 0;
for (int offset = 0; offset < k; offset++) {
minimum += values[start + offset];
maximum += values[n - 1 - offset];
}
if (target < minimum || target > maximum) {
return result;
}
if (k == 2) {
int left = start;
int right = n - 1;
while (left < right) {
long sum = (long) values[left] + values[right];
if (sum == target) {
result.add(List.of((long) values[left], (long) values[right]));
left++;
right--;
while (left < right && values[left] == values[left - 1]) {
left++;
}
while (left < right && values[right] == values[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
for (int i = start; i <= n - k; i++) {
if (i > start && values[i] == values[i - 1]) {
continue;
}
long smallest = values[i];
long largest = values[i];
for (int offset = 1; offset < k; offset++) {
smallest += values[i + offset];
largest += values[n - offset];
}
if (target < smallest) {
break;
}
if (target > largest) {
continue;
}
List<List<Long>> suffixes = search(
values, i + 1, k - 1, target - values[i]
);
for (List<Long> suffix : suffixes) {
List<Long> combination = new ArrayList<>(k);
combination.add((long) values[i]);
combination.addAll(suffix);
result.add(combination);
}
}
return result;
}
}
对于三数之和，调用 kSum(values, 3, 0)。返回类型使用 Long，避免组合求和超过 int 时发生溢出。若题目只要求输出原数组下标，排序时还需同时保存原下标，不能只返回排序后位置。
七、Python 实现：通用 k 数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from __future__ import annotations
def k_sum(values: list[int], k: int, target: int) -> list[list[int]]:
if values is None:
raise ValueError("values must not be None")
if k < 2:
raise ValueError("k must be at least 2")
nums = sorted(values)
def search(start: int, count: int, remaining: int) -> list[list[int]]:
result: list[list[int]] = []
if len(nums) - start < count:
return result
smallest = sum(nums[start : start + count])
largest = sum(nums[len(nums) - count :])
if remaining < smallest or remaining > largest:
return result
if count == 2:
left, right = start, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == remaining:
result.append([nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < remaining:
left += 1
else:
right -= 1
return result
for i in range(start, len(nums) - count + 1):
if i > start and nums[i] == nums[i - 1]:
continue
min_sum = nums[i] + sum(nums[i + 1 : i + count])
max_sum = nums[i] + sum(nums[len(nums) - count + 1 :])
if remaining < min_sum:
break
if remaining > max_sum:
continue
for suffix in search(i + 1, count - 1, remaining - nums[i]):
result.append([nums[i], *suffix])
return result
return search(0, k, target)
assert k_sum([-4, -1, -1, 0, 2, 5], 3, 0) == [
[-4, -1, 5],
[-1, -1, 2],
]
assert k_sum([1, 2], 3, 3) == []
assert k_sum([0, 0, 0, 0], 3, 0) == [[0, 0, 0]]
Python 的整数不会发生固定宽度溢出，但大型输入仍要考虑时间和内存。上面的递归按 k 层固定元素，最后落到双指针的两数和。
八、复杂度分析与适用边界
三数之和的排序加双指针：
- 排序：
O(n log n)； - 固定一个数并扫描剩余区间：
O(n²)； - 总时间：
O(n²)； - 排序是否原地、结果列表占用的空间取决于语言实现和输出规模。
通用 k 数之和的复杂度取决于 k 和输出数量。固定 k - 2 个元素后用双指针，粗略上界常写作 O(n^(k-1))（不计排序和输出成本）；k 越大，组合数量增长越快。
当题目只要求判断是否存在一组，或只要最小/最大值时，不一定需要生成所有组合。明确输出要求，避免保存不必要的结果。
九、常见错误
- 固定元素后仍从数组开头开始找：会重复使用同一元素或生成乱序组合，双指针范围应从
i + 1开始。 - 去重条件写成
i > 0：应与当前递归层起点比较，保留同一组合中合法的重复值。 - 找到答案后只移动一个指针：重复值可能再次生成同一组合；两边移动并跳过重复值。
- 把下标组合和数值组合混为一谈：排序后值组合便于去重，但原始下标需要额外映射。
- 求和使用窄整数类型：多个大整数相加可能溢出，比较前应提升类型。
- 过度剪枝：
break只适用于后续固定值也不可能满足的下界；若只是当前值偏小，应continue。 - 忽略元素不足：递归前要确认剩余元素数至少为
k。
十、与后续主题的连接
N 数之和把哈希表和双指针的思路串在一起：哈希表提供“寻找补数”的视角，排序提供单调性，双指针则高效处理最后两个数。排序还帮助去重和剪枝，因此下一阶段遇到无序输入时，排序不只是格式整理，而是为后续算法建立可利用的结构。
下一篇将把双指针用于原地筛选：通过读写指针移除指定元素，并维护“有效前缀”不变量。
小结
N 数之和的通用套路是：排序、递归固定前 k - 2 个数、最后用双指针解决两数之和。排序后的最小/最大和可以剪枝；固定层和双指针命中后都要按正确边界去重。最重要的是区分值组合与原始下标，并在求和时考虑整数溢出。