Given an array of integers, find two numbers such that they add up to a specific target number.

The functiontwoSumshould return_indices_of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) areNOTzero-based.

Notice

You may assume that each input would have exactly one solution

Have you met this question in a real interview?

Yes

Example

numbers=[2, 7, 11, 15], target=9

return[1, 2]

1. two pointer

two pointers moving towards each other. array must be sorted

1. check the head + tail value if smaller than target, then move the head forward will have a increase that's smaller than all other increase
2. check the head + tail value if larger than move the tail backwards will have a decrease that's smaller than all other decrease

public class Solution {
    /*
     * @param numbers: An array of Integer
     * @param target: target = numbers[index1] + numbers[index2]
     * @return: [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] numbers, int target) {
        // write your code here
        int[] numCopy = new int[numbers.length];
        int[] ans = new int[2];
        for (int k = 0; k < numbers.length; k++) {
            numCopy[k] = numbers[k];
        }

        int i = 0;
        int j = numbers.length - 1;
        Arrays.sort(numCopy);
        while (i < j) {
            if ((numCopy[i] + numCopy[j]) == target) {
                break;
            } else if ((numCopy[i] + numCopy[j]) < target) {
                i++;
            } else {
                j--;
            }
        }
        for (int p = 0, q = 0; p < numbers.length && q < 2; p++) {

            if (numCopy[i] == numbers[p] || numCopy[j] == numbers[p]) {
                ans[q] = p + 1;
                q++;
            }
        }
        return ans;
    }
}

public class Solution {
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1 + 1, index2 + 1] (index1 < index2)
     */

    //two sum two pointer
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                map.get(numbers[i]).add(i + 1);
                continue;
            }
            List<Integer> newList = new ArrayList<>();
            newList.add(i + 1);
            map.put(numbers[i], newList);
        }

        Arrays.sort(numbers);
        int i = 0;
        int j = numbers.length - 1;
        int[] ans = new int[2];
        while (i <= j) {
            if (numbers[i] + numbers[j] == target) {
                if (numbers[i] != numbers[j]) {
                    ans[0] = map.get(numbers[i]).get(0);
                    ans[1] = map.get(numbers[j]).get(0);
                } else {
                    for (int q = 0; q < 2; q++) {
                        ans[q] = map.get(numbers[i]).get(q);
                    }
                }
                Arrays.sort(ans);
                return ans;
            } else if (numbers[i] + numbers[j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return ans;

    }



    //method 1 hashmap
    //disadvantage is there is a O(n) space complexity
    /*
    public int[] twoSum(int[] numbers, int target) {
        // write your code here
        int[] result = new int[2];
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        HashMap<Integer, Integer> memo = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (memo.containsKey(target - numbers[i])) {
                result[0] = memo.get(target - numbers[i]);
                result[1] = i + 1;
                return result;
            }
            memo.put(numbers[i], i + 1);
        }
        return null;
    }
    */

    /*
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        int[] copy = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            copy[i] = numbers[i];
        }
        Arrays.sort(numbers);
        int left = 0;
        int right = numbers.length - 1;
        int[] result = new int[2];
        while (left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                if (numbers[left] != numbers[right]) {
                    int leftIn = 0;
                    int rightIn = 0;
                    for (int i = 0; i < copy.length; i++) {

                        if (copy[i] == numbers[left]) {
                            leftIn = i + 1;
                        } else if (copy[i] == numbers[right]) {
                            rightIn = i + 1;
                        }
                    }
                    result[0] = Math.min(leftIn, rightIn);
                    result[1] = Math.max(leftIn, rightIn);
                    return result;
                } else {
                    boolean isFirst = true;
                    for (int i = 0; i < copy.length; i++) {
                        if (isFirst && copy[i] == numbers[left]) {
                            result[0] = i + 1;
                            isFirst = false;
                        }
                        else if (!isFirst && copy[i] == numbers[right]) {
                            result[1] = i + 1;
                            return result;
                        }

                    }
                }
            }
        }      
        return null;
    }
    */

}