哈希表法:
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),因此整个算法的效率非常高。这个算法的关键在于利用哈希表来存储已经遍历过的元素,以便快速查找它们的补数。这种方法比使用嵌套循环来比较所有可能的元素对要高效得多。
本文含有隐藏内容,请 开通VIP 后查看