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 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免费学习笔记（深入）”；
-
第一次迭代 (i = 0):
- map 是空的。
- complement = target - nums[0]。
- map.containsKey(complement) 被调用。由于 map 为空，它会返回 false。
- if 块不会执行。
- 执行 map.put(nums[0], 0)。此时，nums[0] 和它的索引 0 被添加到 map 中。map 不再为空。
-
第二次迭代 (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 中。
-
后续迭代:
- 此过程持续进行。在每次迭代中，containsKey() 都会检查当前元素 nums[i] 所需的“配对数”（即 target - nums[i]）是否已经存在于 map 中。
- map 中存储的是所有已经遍历过的元素及其索引。因此，当 containsKey() 找到匹配项时，它总能找到一个之前出现过的元素与当前元素构成目标和。
示例代码分析
- Map
map = new HashMap();: 创建一个空的哈希映射，用于存储数组元素的值及其对应的索引。键是数组元素的值，值是该元素在数组中的索引。 - for (int i = 0; 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 是其基本且一致的行为，而算法的精妙之处在于如何利用这种行为，通过迭代逐步填充数据结构，从而解决问题。
