数组求和问题（N-Sum）是算法面试中经久不衰的经典题型。从最基础的 Two Sum 到进阶的 kSum，其核心本质往往殊途同归。本文将以资深工程师的视角，系统梳理 2Sum、3Sum、3Sum Closest 及 4Sum 的解题演进之路，探讨如何通过双指针与剪枝策略将时间复杂度压榨至极限。
通用解题模式#
在深入具体代码之前，我们要建立一个全局视角。这类问题通常可以归纳为以下三种模式：
- 确定性问题：如 Two Sum，寻找精确的目标解。
- 最优化问题：如 3Sum Closest，寻找与目标最接近的解。
- 组合问题：如 4Sum，寻找所有满足条件的不重复元组。
核心优化方向永远是围绕时间复杂度进行的：
- 空间换时间：利用哈希表将 $O(n)$ 查找优化至 $O(1)$。
- 排序 + 双指针：这是解决 N-Sum 问题的“银弹”。通过排序将无序数组转化为有序，从而利用双指针的单调性，将 $O(n^k)$ 的复杂度降低至 $O(n^{k-1})$。
- 剪枝（Pruning）：在搜索过程中提前剔除不可能的分支，这在 N > 2 时尤为重要。
1. Two Sum：万法之源#
LeetCode 1 | 链接
这是所有人的算法起点，但它引出了两个最基本的流派。
核心思路#
- 暴力法：双层循环，最直观但效率最低，时间复杂度 $O(n^2)$。
- 哈希表（最优解）：利用 Map 记录遍历过的元素
{value: index}，在遍历 nums[i] 时，直接查找 target - nums[i] 是否存在。
Go 最佳实践#
工程代码中，我们直接采用哈希表法，这在这一层面上是时间最优的。
1
2
3
4
5
6
7
8
9
10
11
| func twoSum(nums []int, target int) []int {
// 预分配 map 空间可微容易减少 rehash 开销，虽非必须但为好习惯
seen := make(map[int]int, len(nums))
for i, num := range nums {
if j, exists := seen[target-num]; exists {
return []int{j, i}
}
seen[num] = i
}
return nil
}
|
2. Three Sum：排序与双指针的艺术#
LeetCode 15 | 链接
从两数之和到三数之和，题目难度陡增。主要难点在于去重。如果沿用哈希表法，去重逻辑会非常复杂且难以维护。此时，排序 + 双指针成为了标准解法。
核心思路#
- 排序：首先对数组进行排序。这是使用双指针和去重的前提。
- 固定一位：遍历数组，固定枚举
nums[i]。 - 双指针汇聚：在
i 后面的区间 [i+1, n-1] 中，设置左右指针 left 和 right，寻找 nums[left] + nums[right] == -nums[i]。 - 极致剪枝：
- 提前退出：如果
nums[i] > 0，由于数组已排序，后续不可能再有数字之和等于 0。 - 跳过重复：无论是固定的
i，还是移动的 left 和 right，遇到相同数值必须跳过，以避免产生重复结果。
Go 实现#
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
| func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
// 预估容量，避免频繁扩容
result := make([][]int, 0, n/3)
for i := 0; i < n-2; i++ {
// 剪枝 1: 最小的数都大于 0，没戏了
if nums[i] > 0 {
break
}
// 剪枝 2: i 去重
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
// 剪枝 3: left 和 right 去重
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return result
}
|
3. Three Sum Closest：最优化搜索#
LeetCode 16 | 链接
解题思路#
这道题是 3Sum 的变体。区别在于我们需要维护一个全局变量来记录当前的最小差距（gap）。框架依然是 排序 + 双指针，只是循环内部的逻辑不再是寻找相等，而是不断更新“最接近”的值。
Go 实现#
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
| func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
n := len(nums)
// 初始化一个足够大的差距或者是第一次的结果
closest := nums[0] + nums[1] + nums[2]
for i := 0; i < n-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
// 发现更接近的值，更新快照
if abs(sum-target) < abs(closest-target) {
closest = sum
}
if sum == target {
return sum
} else if sum < target {
left++
} else {
right--
}
}
}
return closest
}
func abs(x int) int {
if x < 0 { return -x }
return x
}
|
4. Four Sum：递归与泛化#
LeetCode 18 | 链接
解题思路#
四数之和虽然看起来更可怕，但本质上只是在 3Sum 外面再套了一层循环。它的时间复杂度是 $O(n^3)$。
降维思想：
- 2Sum: $O(n)$ (Hash) 或 $O(n \log n)$ (Sort)
- 3Sum: 固定 1 个数 -> 2Sum ($O(n^2)$)
- 4Sum: 固定 1 个数 -> 3Sum -> 2Sum ($O(n^3)$)
- kSum: 递归降维至 2Sum。
Go 实现#
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
| func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n := len(nums)
result := make([][]int, 0)
for i := 0; i < n-3; i++ {
// 剪枝 1: 最小值剪枝
if i > 0 && nums[i] == nums[i-1] { continue }
// 剪枝 2: 数值范围剪枝（进阶优化，可选）
// 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 }
left, right := j+1, n-1
for left < right {
sum := nums[i] + nums[j] + nums[left] + nums[right]
if sum == target {
result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] { left++ }
for left < right && nums[right] == nums[right-1] { right-- }
left++
right--
} else if sum < target {
left++
} else {
right--
}
}
}
}
return result
}
|
总结与思考#
| 问题 | 最佳解法 | 时间复杂度 | 核心考点 |
|---|
| 2Sum | 哈希表 | $O(n)$ | 空间换时间 |
| 3Sum | 排序 + 双指针 | $O(n^2)$ | 去重、双指针单调性 |
| 4Sum | 排序 + 双层循环 + 双指针 | $O(n^3)$ | 降维思想、剪枝 |
工程启示：
在处理海量数据的匹配问题时，排序往往是化繁为简的第一步。虽然它带来了 $O(n \log n)$ 的开销，但带来的有序性使得后续的查找和去重效率呈指数级优化。此外，剪枝思想在任何搜索类算法中都是提升性能的关键——永远不要计算那些注定无效的结果。