深入理解Two Sum问题中HashMap的containsKey()行为

本文深入探讨了在解决Two Sum问题时，如何高效利用Hashmap来查找目标数字对。重点解释了初学者常遇到的疑惑：一个空的HashMap如何通过containsKey()方法返回true。我们将通过详细的代码分析和执行流程，阐明HashMap在迭代过程中逐步填充的机制，从而实现高效的查找逻辑，并揭示其背后的原理。

在计算机科学中，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。

1. 初始化： map 为空 {}, result 为 [0, 0]。

2. 第一次循环 (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}。

3. 第二次循环 (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 问题中扮演着核心角色，它通过动态构建一个查找表，实现了高效的问题求解。