[Leetcode] Two Sum

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

The function twoSum should 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) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

The most naive method is to enumerate all possible combinations of two elements in the array, which give O(n^2) time complexity and O(1) space complexity. Another elegant method is to use a HashMap to store what we have and we look up (target - key) in it. We store the number and its index in the HashMap and use the number as the key. A special case is that the key's index should not be the same with (target - key)'s index, for example, 2 1 3 and target is 4. So what we need to do is keep the last time a key is shown in the array, and we sweep from front to end, in this way, case like 2 2 2, 4 would give a right answer.

    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        if(n < 2)
            return null;
        HashMap<Integer, Integer> map =  new HashMap<Integer, Integer>();
        
        for(int i = 0; i < n; i++) {
            map.put(numbers[i], i);
        }
        int[] res = new int[2];
        for(int i = 0; i < n; i++) {
            if(map.containsKey(target - numbers[i]) == true && map.get(target - numbers[i]) != i) {
                int ind = map.get(target - numbers[i]);
                res[0] = (ind < i) ? (ind + 1) : (i + 1);
                res[1] = (ind < i) ? (i + 1) : (ind + 1);
            }
        }
        
        return res;
    }