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

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

   

   Kotlin Android 中文开发帮助文档 PDF版

   这本书并不是一本语言参考书，但它是一个Android开发者去学习Kotlin并且使用在自己项目中的一个工具。我会通过使用一些语言特性和有趣的工具和库来解决很多我们在日常生活当中都会遇到的典型问题。 这本书是非常具有实践性的，所以我建议你在电脑面前跟着我的例子和代码实践。无论何时你都可以在有一些想法的时候深入到实践中去。 这本书适合你吗？ 写这本书是为了帮助那些有兴趣 使用Kotlin语言来进行开发的Android开发者。 如果你符合下面这些情况，那这本书是适合你的： 你有相关Android开发和Andro

   11

   查看详情

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

以上就是深入理解Two Sum问题中HashMap的containsKey()行为的详细内容，更多请关注php中文网其它相关文章！