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。