1刷
HashMap
Time complexity O(n), Space complexity: O(n)
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = {-1, -1};
if(nums == null || nums.length == 0) return res;
Map<Integer, Integer>map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(!map.containsKey(target - nums[i])){
map.put(nums[i], i);
}
else{
res[0] = i;
res[1] = map.get(target - nums[i]);
return res;
}
}
return res;
}
}
Binary Search
或者可以先sort数组，再用双指针找target - numbers[i]。这样的话Time Complexity 应该是是O(nlogn)， Space Complexity是O(n)，就是时间复杂度换空间复杂度。 要注意sort之后原数组的index也会改变，要找到好的方法保存原数组的index。
