在计算机科学中，two sum问题是一个经典的数组操作问题：给定一个整数数组 nums 和一个目标值 target，请找出数组中和为 target 的两个整数的下标。解决此问题有多种方法，其中基于哈希表（如java中的hashmap）的解决方案因其卓越的时间效率（o(n)）而广受欢迎。然而，对于初学者而言，该解决方案中hashmap的containskey()方法在一个看似为空的映射上如何工作，常常会引起困惑。
HashMap.containsKey()方法的工作机制
首先，需要明确HashMap.containsKey(key)方法的行为：当对一个空的HashMap调用containsKey()方法时，无论传入任何key，它都将始终返回false。这是因为一个空的哈希映射中不包含任何键值对，自然也无法找到任何指定的键。这与查阅一本空电话簿的逻辑是一致的——如果你问一本空电话簿中是否有某个名字，答案必然是否定的。
Two Sum算法中的HashMap应用原理
Two Sum问题的HashMap解决方案巧妙之处在于其迭代过程。算法的核心思想是：对于数组中的每一个数字 num，我们计算出它与 target 的差值 complement = target - num。如果这个 complement 已经在我们之前遍历过的数字中出现过，那么我们就找到了符合条件的两个数字。HashMap在这里的作用就是快速查找这个 complement 是否存在以及它对应的索引。
让我们来看一下经典的Java实现代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>(); // 初始化一个空的HashMap
int[] result = new int[2];
for (int i = 0; i < n; i++) { // 遍历数组
// 步骤1: 检查当前数字的“补数”是否已存在于map中
if (map.containsKey(target - nums[i])) {
result[1] = i; // 当前数字的索引
result[0] = map.get(target - nums[i]); // 补数的索引
return result; // 找到即返回
}
// 步骤2: 将当前数字及其索引放入map
map.put(nums[i], i);
}
return result; // 如果没有找到，返回默认结果（实际问题中通常保证有解）
}
}代码执行流程分析
初学者疑惑的关键点在于，map 在循环开始时是空的，那么 map.containsKey(target - nums[i]) 怎么可能返回 true 呢？答案在于 map.put(nums[i], i) 这行代码的位置和循环的迭代特性。
我们通过一个例子来逐步分析： 假设 nums = [2, 7, 11, 15]，target = 9。
初始化： map 为空 {}, result 为 [0, 0]。
-
第一次循环 (i = 0, nums[0] = 2):
- 计算 complement = target - nums[0] = 9 - 2 = 7。
- 执行 map.containsKey(7)：此时 map 是空的 {}, 所以 containsKey() 返回 false。
- 执行 map.put(nums[0], 0)：将 (2, 0) 加入 map。现在 map 为 {2: 0}。
-
第二次循环 (i = 1, nums[1] = 7):
- 计算 complement = target - nums[1] = 9 - 7 = 2。
- 执行 map.containsKey(2)：此时 map 为 {2: 0}，containsKey() 发现键 2 存在，返回 true。
- 进入 if 块：
- result[1] = i，即 result[1] = 1。
- result[0] = map.get(2)，即 result[0] = 0。
- return result，返回 [0, 1]。
从这个例子可以看出，在第一次循环中，containsKey() 确实返回了 false。但关键在于，每次循环的最后，当前的数字及其索引会被添加到 map 中。 这意味着，从第二次循环开始，map 就可能包含之前遍历过的数字。当 containsKey() 被调用时，它检查的是 map 中到目前为止已经添加的所有元素，而不是一个始终为空的映射。
总结与注意事项
- 动态填充： HashMap 在 Two Sum 解决方案中并非一直为空，而是在每次迭代中动态地填充数据。containsKey() 检查的是当前 map 的状态，而不是初始状态。
- 时间复杂度： 这种方法将时间复杂度从暴力解法的 O(N^2) 降低到 O(N)，因为 HashMap 的 containsKey() 和 put() 操作的平均时间复杂度都是 O(1)。
- 空间复杂度： 该方法需要额外的 O(N) 空间来存储 HashMap。
- 顺序性： 这种迭代方式保证了我们总是先检查 complement 是否存在，如果不存在，再将当前元素加入 map。这避免了将当前元素与自身匹配的错误，并确保找到的索引是正确的。
通过理解这种迭代填充的机制，我们可以清楚地看到，HashMap.containsKey() 在 Two Sum 问题中扮演着核心角色，它通过动态构建一个查找表，实现了高效的问题求解。
