问题描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解决思路
将数组元素和下标分别作为Key-Value对，存在HashMap中，if判断寻找是否有符合条件的元素。
问题解惑
- 为什么不是先将元素放入map，再判断是否有元素符合条件？ 因为，如果先放进去，可能会重复使用自身，比如[3,2,4],target = 6时，会认为3+3等于6，而这是不正确的。
- 有人提到，[2,5,5,12] target = 10这种，有两个5，而HashMap的key是不可重复的，一旦重复，value会被覆盖，会不会造成键值对冲突？
其实这个问题我之前没想到，后来想了一下，刚好也是被问题1解决了，即先判断，再放。第二个5实际上并没有放进去，因为再放进去之前，if判断已经把这题解决掉了。
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
//corner case
if(nums.length < 2 || nums == null){
return new int[]{-1, -1};
}
HashMap<Integer, Integer> map = new HashMap<>();
int[] res = new int[]{-1, -1};
for(int i = 0; i < nums.length; i++){
//judge eligible conditions
if(map.containsKey(target - nums[i])){
res[0] = map.get(target - nums[i]);
res[1] = i;
break;
}
//if not eligible, put the element to the map
map.put(nums[i], i);
}
return res;
}
}
复杂度分析
时间复杂度： O(n)
空间复杂度： O(n)
