8
0
0
梦开始的地方-两数之和
文章摘要
|
思路
标签：哈希映射
这道题最简单的解法其实是通过暴力枚举，但是这样时间复杂度在 O(n2)
而我们知道哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 来降低时间复杂度
遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值
如果存在则找到了两个值,返回【另一半的下标】和【当前i】,如果不存在则就把当前数字和下标存入哈希表，留给后面循环查找，继续遍历直到找到为止
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap()<>;
for(int i = 0; i < hashtable.length; i++){
if(hashtable.containKey(target - nums[i]){
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i],i);
}
return new int[0];
}
}