1. 概述
在本篇文章中，我们将探讨三种不同的方法来解决一个经典问题：判断一个整数数组中是否存在两个数，它们的和等于给定的目标值。
我们将从最基础的暴力解法开始，然后逐步优化，介绍两种更高效的解决方案：一种是使用排序+双指针技巧，另一种是使用哈希表（Hash Table）来换取时间效率的提升。
虽然问题本身看起来简单，但在实际编码中稍有不慎就可能踩坑。所以，这篇文章适合有一定经验的开发者参考，尤其是希望加深对数组处理和时间复杂度理解的同学。
2. 问题描述
给定一个未排序的整数数组 nums 和一个整数目标值 target，我们需要判断数组中是否存在两个不同的数，它们的和恰好等于 target。如果存在这样的两个数，返回 true；否则返回 false。
注意：这两个数不能是同一个元素（即不能自己加自己）。
✅ 示例 1：存在满足条件的两个数
- 输入：nums = [10, 5, 15, 7, 14, 1, 9]，target = 6
- 输出：true
- 说明：nums[1] + nums[5] = 5 + 1 = 6，满足条件。
❌ 示例 2：不存在满足条件的两个数
- 输入：nums = [10, 5, 15, 7, 14, 1, 9]，target = 27
- 输出：false
- 说明：遍历所有组合后没有找到和为 27 的两个数。
3. 暴力解法（Brute Force）
最直观的思路是使用双重循环，遍历数组中所有两两组合，判断是否有和等于目标值。
✅ 实现思路
- 外层循环控制第一个数 i
- 内层循环控制第二个数 j（j > i，避免重复计算）
- 判断 nums[i] + nums[j] == target
Java 示例代码
public boolean hasPairWithSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return true;
}
}
}
return false;
}
⏱️ 时间复杂度
- 最坏情况下，每个元素都要和其他所有元素配对，时间复杂度为 O(n²)
🧠 空间复杂度
- 只使用了常数级额外空间，空间复杂度为 O(1)
4. 优化解法
4.1. 排序 + 双指针法（Sorting + Two Pointers）
如果允许对数组进行排序，我们可以使用双指针技巧来降低时间复杂度。
✅ 实现思路
- 将数组排序（升序）
- 定义两个指针：left 指向数组头部，right 指向尾部
- 循环判断 nums[left] + nums[right] 与 target 的关系：
- 等于：返回 true
- 小于：left 右移
- 大于：right 左移
Java 示例代码
public boolean hasPairWithSum(int[] nums, int target) {
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return true;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return false;
}
⏱️ 时间复杂度
- 排序：O(n log n)
- 双指针遍历：O(n)
- 总体时间复杂度：O(n log n)
🧠 空间复杂度
- 常数级额外空间：O(1)
⚠️ 注意：此方法会修改原始数组顺序。如果不能修改原始数组，需要先拷贝一份再排序。
4.2. 使用哈希表（Hash Table）
如果我们愿意使用额外的空间，就可以将查找效率提升到线性级别。
✅ 实现思路
- 遍历数组时，对于每个元素 nums[i]，计算 target - nums[i] 得到 diff
- 如果 diff 在哈希表中存在，说明找到了匹配对，返回 true
- 否则将当前元素 nums[i] 存入哈希表中
Java 示例代码
public boolean hasPairWithSum(int[] nums, int target) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
int diff = target - num;
if (seen.contains(diff)) {
return true;
}
seen.add(num);
}
return false;
}
⏱️ 时间复杂度
- 每个元素只被访问一次，查找和插入都是 O(1)，总体时间复杂度为 O(n)
🧠 空间复杂度
- 最多存储 n 个元素，空间复杂度为 O(n)
✅ 这是三种方法中时间效率最高的一种，适合对性能要求较高的场景。
5. 总结
我们从暴力解法入手，逐步引入了两种优化方案：
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改数组 |
|---|---|---|---|
| 暴力法 | O(n²) | O(1) | ❌ |
| 排序+双指针 | O(n log n) | O(1) | ✅（排序会修改） |
| 哈希表 | O(n) | O(n) | ❌ |
✅ 建议使用场景
- 数组较小或对性能要求不高的场合：使用暴力法
- 允许排序且希望节省空间：使用排序+双指针
- 追求极致性能且可以接受一定空间开销：使用哈希表
✅ 推荐面试中优先使用哈希表方案，因为其思路清晰、代码简洁、效率高，是最常被考察的解法。