Java HashMap在Two Sum问题中的核心机制解析

本文深入探讨了Hashmap在解决Two Sum问题中的应用，尤其关注了HashMap.containsKey()方法在初始为空的映射上的行为。文章阐明了containsKey()对空HashMap返回false的基本原理，并详细解析了Two Sum算法如何通过在迭代过程中动态填充HashMap，从而高效地查找目标差值，实现线性时间复杂度的解决方案。

HashMap.containsKey() 的基本行为

在理解two sum算法之前，首先需要明确hashmap中containskey()方法的核心功能。当对一个hashmap实例调用containskey(key)方法时，它会检查该映射中是否存在指定的键。如果hashmap是空的，即其中不包含任何键值对，那么无论传入何种key，containskey()方法都将返回false。这符合直观逻辑：一个空的容器自然不会包含任何元素。

例如，如果您有一个空的电话簿，当被问及某个特定姓名是否在其中时，答案必然是“否”，因为电话簿中没有任何条目。HashMap的行为与此类似，它会忠实地报告其当前状态。

Two Sum 问题与 HashMap 优化

Two Sum 问题是一个经典的算法面试题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

最直接的解法是使用两层循环，时间复杂度为 O(n²)。然而，利用 HashMap 可以将其优化到 O(n) 的时间复杂度。以下是使用 HashMap 解决 Two Sum 问题的典型 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++) {             // 计算当前元素与目标值的差值             int complement = target - nums[i];               // 检查HashMap中是否已存在这个差值             if (map.containsKey(complement)) {                 // 如果存在，说明找到了配对的两个数                 result[1] = i; // 当前元素的索引                 result[0] = map.get(complement); // 差值对应的元素的索引                 return result; // 返回结果             }             // 将当前元素及其索引放入HashMap             // 供后续迭代使用             map.put(nums[i], i);          }         return result; // 如果没有找到，返回默认结果（通常不会发生，因为题目保证有解）     } }

核心机制解析：HashMap 的动态填充

初学者可能会对上述代码中map.containsKey(target – nums[i])在HashMap初始为空时如何工作感到困惑。关键在于理解HashMap是如何在循环过程中被“动态填充”的。

立即学习“Java免费学习笔记（深入）”；

1. 第一次迭代 (i = 0):

   • map 是空的。
   • complement = target – nums[0]。
   • map.containsKey(complement) 被调用。由于 map 为空，它会返回 false。
   • if 块不会执行。
   • 执行 map.put(nums[0], 0)。此时，nums[0] 和它的索引 0 被添加到 map 中。map 不再为空。

2. 第二次迭代 (i = 1):

   • map 中现在包含 (nums[0], 0)。
   • complement = target – nums[1]。
   • map.containsKey(complement) 被调用。此时，map 会检查 complement 是否等于 nums[0]。
     • 如果 complement 等于 nums[0]，说明 nums[0] 和 nums[1] 之和恰好是 target。containsKey() 返回 true，找到解。
     • 如果 complement 不等于 nums[0]，containsKey() 返回 false。
   • 无论结果如何，map.put(nums[1], 1) 将 nums[1] 和它的索引 1 添加到 map 中。

3. 后续迭代:

   • 此过程持续进行。在每次迭代中，containsKey() 都会检查当前元素 nums[i] 所需的“配对数”（即 target – nums[i]）是否已经存在于 map 中。
   • map 中存储的是所有已经遍历过的元素及其索引。因此，当 containsKey() 找到匹配项时，它总能找到一个之前出现过的元素与当前元素构成目标和。

示例代码分析

• Map<Integer, Integer> map = new HashMap<>();: 创建一个空的哈希映射，用于存储数组元素的值及其对应的索引。键是数组元素的值，值是该元素在数组中的索引。
• for (int i = 0; i < n; i++): 遍历整个数组。
• int complement = target – nums[i];: 计算当前元素 nums[i] 需要的“补数”，即另一个数，使得 nums[i] 加上它等于 target。
• if (map.containsKey(complement)): 这是算法的核心。它检查之前遍历过的元素中是否存在这个“补数”。由于 HashMap 的平均查找时间复杂度为 O(1)，这一步非常高效。
• result[1] = i; result[0] = map.get(complement);: 如果找到了补数，说明当前元素 nums[i] 和 map.get(complement)（即补数对应的元素）就是我们要找的两个数。map.get(complement) 会返回补数在数组中的原始索引。
• map.put(nums[i], i);: 在检查完当前元素后，将其添加到 HashMap 中。这样，在后续的迭代中，如果某个元素需要 nums[i] 作为它的补数，就可以在 map 中找到。

注意事项与总结

• 动态构建: HashMap 在 Two Sum 算法中并非一开始就包含所有元素，而是在循环过程中逐步构建的。每次迭代，我们都将当前元素添加到 HashMap 中，以便后续元素可以查找它。
• 时间复杂度优势: HashMap 的 containsKey() 和 put() 操作的平均时间复杂度都是 O(1)。因此，整个 Two Sum 算法的时间复杂度为 O(n)，其中 n 是数组的长度，这比 O(n²) 的暴力解法效率高得多。
• 空间复杂度: HashMap 需要额外的空间来存储元素，最坏情况下（所有元素都不同）空间复杂度为 O(n)。
• 应用场景: 这种利用哈希表进行“查找-存储”模式的策略在许多需要快速查找配对元素的问题中非常常见，例如三数之和、四数之和等。
• 理解数据结构行为: 深入理解数据结构（如 HashMap）的基本行为及其在算法中的动态变化，是编写高效、正确代码的关键。对于一个空的 HashMap，containsKey() 返回 false 是其基本且一致的行为，而算法的精妙之处在于如何利用这种行为，通过迭代逐步填充数据结构，从而解决问题。