1. 问题概述
3Sum 是算法领域中一个经典问题，广泛应用于复杂度分析、组合优化、以及算法设计教学中。其核心在于从一个整数数组中找出是否存在三个数，其和等于给定目标值。这个问题的变种很多，本文将聚焦于以下版本：
给定一个整数数组 a = [a₁, a₂, ..., aₙ] 和一个目标值 s，是否存在三个元素 aᵢ, aⱼ, aₖ（其中 i ≠ j ≠ k），使得它们的和等于 s？每个元素只能在三元组中出现一次。
例如：若 a = [1, 0, 3, 17, 7]，且 s = 21，则有效三元组为 [1, 3, 17]。
2. 3Sum 的重要性
3Sum 问题在算法复杂度理论中具有重要意义。许多计算几何、动态图、字符串匹配等问题都可以归约（reduce）到 3Sum 上。这意味着，如果我们能解决这些新问题，就可以用它们来解决 3Sum 问题。
因此，3Sum 可以被视为一个“下界”问题：如果某个问题比 3Sum 更难（即 3Sum 可以归约到它），那么它的最优解的时间复杂度至少不低于 3Sum 的最优解。
3. 暴力解法
最直观的解法是使用三重循环，遍历所有三元组组合，判断是否存在和为 s 的组合。
public static boolean bruteForce3Sum(int[] a, int s) {
int n = a.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] == s) {
return true;
}
}
}
}
return false;
}
✅ 优点：
- 实现简单
- 逻辑清晰
❌ 缺点：
- 时间复杂度为
O(n³)，效率极低 - 不适合处理大规模数据
4. 优化解法：O(n²)
为了提升效率，可以使用哈希表来优化查找第三个数的步骤。其核心思想是：
对于任意两个数
a[i]和a[j]，我们只需要判断是否存在一个数x = s - (a[i] + a[j])在数组中即可。
我们可以先将数组中的所有元素存入哈希表中，这样查找 x 是否存在只需要 O(1) 时间。
public static boolean optimized3Sum(int[] a, int s) {
Set<Integer> set = new HashSet<>();
for (int num : a) {
set.add(num);
}
int n = a.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int complement = s - a[i] - a[j];
if (set.contains(complement)) {
if (complement != a[i] && complement != a[j]) {
return true;
} else {
// 如果 complement 等于 a[i] 或 a[j]，需要确保数组中至少有两次出现
int count = 0;
for (int num : a) {
if (num == complement) count++;
}
if (count >= 2) return true;
}
}
}
}
return false;
}
✅ 优点：
- 时间复杂度降至
O(n²) - 适合中等规模数据
❌ 注意事项：
- 需要额外判断
complement是否等于a[i]或a[j]，防止重复使用同一元素 - 若
complement等于其中一个元素，需确认该元素在数组中出现至少两次
5. 总结
| 方法 | 时间复杂度 | 是否推荐 | 说明 |
|---|---|---|---|
| 暴力解法 | O(n³) |
❌ | 实现简单但效率低，仅用于教学 |
| 哈希优化 | O(n²) |
✅ | 推荐使用，适合大多数实际场景 |
⚠️ 踩坑提醒：
- 不要忽略重复元素的处理，否则可能导致错误判断
- 使用哈希表时，注意是否需要去重或统计出现次数
3Sum 问题虽然看起来简单，但在实际开发中容易踩坑，尤其是在边界条件和重复元素处理上。掌握其优化思路对理解算法设计和复杂度分析非常有帮助。