Two Sum

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.
Example:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

//HashMap, time:O(n), space:O(n)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]);
                res[1] = i;
                break;
            }
            map.put(numbers[i], i);
        }
        return res;
    }
}


/* follow-up1: if the input array is already sorted. */

// two pointers, time:O(n), space:O(1)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                res[0] = left;
                res[1] = right;
                break;
            }
        }
        return res;
    }
}

/*
In the method of two pointers, when the sum is smaller or bigger than the target, the left pointer only pluses one or the right pointer only minuses one. Here we can do some optimization. When the sum is smaller than the target, the left pointer actually can point to the smallest number which equals to or bigger than (target - numbers(right)). When the sum is bigger than the target, the right pointer can point to the biggest number which equals to or smaller than (target - numbers(left)). Because it is the sorted array, we can use binary search to implement this. 

binary search, time:O(logN), space:O(1)
*/

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] ans = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left = binarySearch(numbers, target - 
                       numbers[right], left + 1, right - 1);
            } else if (sum > target) {
                right = binarySearch(numbers, target -                                       numbers[left], left + 1, right - 1);
            } else {
                ans[0] = left;
                ans[1] = right;
                break;
            }
        }
        return ans;
    }
    public int binarySearch(int[] nums, int target, 
                            int left, int right) {
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] > target){
                right = mid;
            } else {
                return mid;
            }
        }
        if (nums[left] >= target) {
            return left;
        }
        return right;
    } 
}


/* follow-up2: if the input array has duplicate numbers, return the indices of two numbers of all the possibilities.
such as: nums = [1,3,5,2,2,3], target = 5,
return:[[1,3],[1,4],[3,5],[4,5]]

Use HashMap, key is number, value is List<Integer> which stores the indices of numbers. And the indices of duplicate numbers will be stored in the same List. 

time:O(n^2), space:O(n)
*/
public class Solution {
    public List<List<Integer>> twoSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
           return ans;
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
               for (Integer index : map.get(target - nums[i])){
                   List<Integer> list = new ArrayList<>();
                  list.add(index);
                  list.add(i);
                  ans.add(list);
               }
           }
           if (map.containsKey(nums[i])) {
map.get(nums[i]).add(i);
           } else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(nums[i], list);
           }
}
return ans;
    }
}