LeetCode 经典问题：数组求和系列详解与分析#
数组求和问题是算法面试中的经典题型，本文将从基础到进阶，系统地分析 2Sum、3Sum、3Sum Closest 和 4Sum 的解题思路、代码实现及优化方案。
通用解题思路分析#
在开始具体问题之前，我们先总结这类问题的通用解题模式：
问题分类
- 确定性问题：寻找具体的和（如 Two Sum）
- 最优化问题：寻找最接近的和（如 3Sum Closest）
- 组合问题：寻找所有可能的组合（如 3Sum、4Sum）
常用技巧
- 排序 + 双指针：解决大多数 nSum 问题的标准方法
- 哈希表：优化查找过程
- 剪枝：去重和提前退出
时间复杂度优化方向
- 使用哈希表将 O(n) 的查找优化为 O(1)
- 通过排序启用双指针，将 O(n²) 优化为 O(nlogn)
- 利用剪枝减少不必要的计算
1. Two Sum (两数之和) [LeetCode 1]#
问题描述#
给定一个整数数组 nums 和目标值 target，找出数组中和为 target 的两个数的下标。
解题思路#
- 暴力解法
- 双层循环遍历所有可能的组合
- 时间复杂度 O(n²)，空间复杂度 O(1)
- 哈希表优化
- 使用哈希表存储遍历过的数字
- 查找当前数字的互补数是否存在
- 时间复杂度 O(n)，空间复杂度 O(n)
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
| // 方法一：暴力解法
func twoSum1(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if nums[i] + nums[j] == target {
return []int{i, j}
}
}
}
return nil
}
// 方法二：哈希表优化
func twoSum2(nums []int, target int) []int {
hashMap := make(map[int]int)
for i, num := range nums {
if j, exists := hashMap[target-num]; exists {
return []int{j, i}
}
hashMap[num] = i
}
return nil
}
|
最佳实践#
选择合适的解法
- 数据量小时可以使用暴力解法
- 数据量大时优先使用哈希表解法
代码优化点
- 提前判断数组长度
- 使用合适的数据结构（map vs slice）
- 考虑内存使用（空间复杂度）
2. Three Sum (三数之和) [LeetCode 15]#
问题描述#
给定一个整数数组，找出所有和为 0 的三元组，要求不能包含重复的三元组。
解题思路#
排序 + 双指针
- 先对数组排序
- 固定一个数，使用双指针查找另外两个数
- 注意去重处理
优化策略
- 提前退出：当固定数字大于 0 时可以结束
- 跳过重复元素
- 收缩边界优化
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
41
| func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
result := make([][]int, 0)
for i := 0; i < n-2; i++ {
// 优化1: 第一个数大于0，后面不可能有解
if nums[i] > 0 {
break
}
// 优化2: 跳过重复数字
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: 跳过重复元素
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]#
问题描述#
给定一个整数数组和目标值 target，找出三个数之和与目标值最接近的结果。
解题思路#
- 排序 + 双指针
- 类似 3Sum，但需要记录最接近的和
- 根据差值判断移动方向
- 优化方向
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
| 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++ {
// 优化1: 跳过重复元素
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]#
问题描述#
给定一个整数数组和目标值 target，找出所有和为 target 的四元组。
解题思路#
- 双循环 + 双指针
- 在 3Sum 的基础上增加一层循环
- 注意去重和剪枝优化
- 优化策略
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
41
42
43
44
45
46
47
48
| 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
}
for j := i+1; j < n-2; j++ {
// 优化3: 跳过重复的第二个数
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
}
|
总结与扩展#
共同特点#
- 解题模式
- 排序 + 双指针是主要解法
- 需要注意去重处理
- 可以通过剪枝优化性能
- 时间复杂度
- Two Sum: O(n) 使用哈希表
- Three Sum: O(n²) 排序后双指针
- Four Sum: O(n³) 在 3Sum 基础上多一层循环
进阶思考#
- 如何扩展到 N Sum 问题？
- 特殊情况处理
- 实际应用场景
- 金融交易匹配
- 数据分析中的模式匹配
- 图像处理中的特征匹配