利用HashMap 减少查询时间
在暴力法中，内层循环查找差值很浪费时间，那么如何减少查询时间呢？利用HashMap 就可以减少查询时间。使用一层循环，每遍历到一个元素就计算该元素与 target 之间的差值，然后HashMap 中寻找该差值，如果找到，则返回两个元素在数组nums 的下标，如果没有找到，则将当前元素存入HashMap中
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
int[] Opt = new int[2];
for (int i = 0; i < nums.length; i++) {
int dif = target - nums[i];
if (map.get(dif) != null) {
Opt[0] = map.get(dif);
Opt[1] = i;
return Opt;
}
map.put(nums[i],i);
}
return Opt;
}
}
//调用hashmap函数，containsKey方法
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
时间复杂度：
O(n)。
网友评论