2Sum

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

solution:

If we use traditional N-Sum solution, we will have to sort the array first, but how about its corresponding index that we want to get? We can solve this by saving those two values and iterate array again to find their indexes. It needs to iterate array twice.
Alternatively, when we meet an O(N) question, we can always think about Hash Map: <value, index >.
For each value1, we check if its corresponding value2 exists in the hash map, which satisfies: value1 + value2 = target. Once found it, return their indexes. 
Tips: HashMap only works on Objects, not primitive types.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] a = new int[2];
        
        // value-> index
        HashMap map = new HashMap();
        
        for(int i = 0; i < numbers.length; i++){
            if(map.containsKey(target - numbers[i])){
                a[0] = map.get(target - numbers[i]);
                a[1] = i+1;
                return a;
            }
            else{
                map.put(numbers[i], i+1);
            }
        }
        return a;
    }
}