【LeetCode】1. 两数之和(Java自用版)
哈希表法：
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for(int i = 0; i < nums.length; i++) {if(hashtable.containsKey(target - nums[i])) {return new int[] {hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}
上面的Java代码是一个有效的解决方案，用于在整数数组nums中找到两个数的索引，使得它们的和等于给定的目标值target。下面是对该代码的详细分析：
- 初始化哈希表：
代码首先创建了一个HashMap（hashtable），其中键是数组中的数字，值是对应数字的索引。这个哈希表用于存储已经遍历过的数组元素，以便在后续的迭代中快速查找它们的补数（即目标值减去当前元素的值）。
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
- 遍历数组：
代码通过for循环遍历数组nums。对于每个元素nums[i]，它执行以下操作：
for(int i = 0; i < nums.length; i++) {
- 查找补数：
在循环内部，代码计算target - nums[i]（即当前元素的补数），然后检查哈希表中是否包含这个补数。
if(hashtable.containsKey(target - nums[i])) {
如果哈希表中存在这个补数，那么它表示已经找到了一个解，即nums[i]和补数对应的元素，它们的和等于target。此时，代码创建一个包含这两个元素索引的整数数组，并返回它。
return new int[] {hashtable.get(target - nums[i]), i};
- 更新哈希表：
如果哈希表中不存在补数，代码将当前元素nums[i]及其索引i添加到哈希表中，以便在后续的迭代中查找。
hashtable.put(nums[i], i);
- 返回空数组：
如果遍历完整个数组后都没有找到满足条件的两个数，那么代码返回一个空的整数数组。
return new int[0];
总结：
这个twoSum方法利用哈希表实现了O(n)时间复杂度的算法，其中n是数组nums的长度。由于哈希表的查找操作平均时间复杂度为O(1)，因此整个算法的效率非常高。这个算法的关键在于利用哈希表来存储已经遍历过的元素，以便快速查找它们的补数。这种方法比使用嵌套循环来比较所有可能的元素对要高效得多。