1. 简介
本文将介绍如何在数组中找到三个数，使得它们的和最接近一个给定的目标数。这是一个常见的算法问题，常见于 LeetCode 等编程平台。我们将从暴力解法入手，再优化到更高效的双指针解法。
2. 问题描述
给定一个整数数组 A 和一个目标整数 t，我们需要在数组中找出三个数，使得它们的和最接近 t。
例如，数组为 {-1, 2, 1, -4}，目标数为 1，则最接近的和为 2，对应的三元组是 {-1, 2, 1}。
3. 暴力解法（Brute Force）
暴力解法的核心思想是枚举所有可能的三元组组合，并记录与目标值最接近的组合。
algorithm threeSumClosest(A, n, t):
// INPUT
// A = an integer array with size n
// t = the target number
// OUTPUT
// Three numbers in A whose sum is closest to t
minDiff <- infinity
result <- []
for i <- 0 to n - 3:
for j <- i + 1 to n - 2:
for k <- j + 1 to n - 1:
sum <- A[i] + A[j] + A[k]
diff <- abs(sum - t)
if diff < minDiff:
minDiff <- diff
result <- [A[i], A[j], A[k]]
return result
✅ 优点：逻辑清晰，实现简单
❌ 缺点：时间复杂度为 O(n^3)，对于大数组效率极低
4. 双指针解法（Two-pointer Approach）
双指针方法是解决此类问题的经典优化手段。该方法依赖于数组的排序，通过固定一个数，然后用双指针扫描剩下的两个数。
4.1 实现思路
- 排序数组：先对数组进行升序排序。
- 固定一个数：遍历数组，每次固定一个元素
A[i]。 - 双指针扫描：使用两个指针
j和k，分别从i+1和n-1开始向中间移动。 - 比较当前和与目标值的差值，更新最接近的三元组。
algorithm threeSumClosest(A, n, t):
// INPUT
// A = an integer array with size n
// t = the target number
// OUTPUT
// Three numbers in A whose sum is closest to t
Sort A in ascending order
minDiff <- infinity
result <- []
for i <- 0 to n - 3:
j <- i + 1
k <- n - 1
while j < k:
sum <- A[i] + A[j] + A[k]
diff <- abs(sum - t)
if diff < minDiff:
minDiff <- diff
result <- [A[i], A[j], A[k]]
if sum < t:
j <- j + 1
else:
k <- k - 1
return result
4.2 时间复杂度分析
- 排序时间：
O(n log n) - 外层循环遍历固定一个数：
O(n) - 内层双指针扫描：
O(n)
总时间复杂度为：O(n^2)，相比暴力解法有显著提升。
5. 总结
| 方法 | 时间复杂度 | 是否推荐 |
|---|---|---|
| 暴力解法 | O(n^3) |
❌ 不推荐用于大数组 |
| 双指针法 | O(n^2) |
✅ 推荐，效率高，实现简单 |
📌 踩坑提示：
- 使用双指针法时，不要忘记先排序数组。
- 注意处理边界条件，比如数组长度小于3的情况。
- 该问题不需要去重，所以不需要跳过重复元素。
如需进一步优化，可考虑使用哈希表或分治法，但双指针已经是最优且最容易实现的方案。