Two Sums Problem | Leet Code

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, and you may not use the same element twice.

 Example:

 Given nums = [2, 7, 11, 15], target = 9,

 Because nums[0] + nums[1] = 2 + 7 = 9,

 return [0, 1].

Code :

/*

Using a HashMap, O(n) space and O(n) time.

    Thinking process:

    Push everything into a HashMap.

    Check if one element exist in the HashMap, if so save it. Meanwhile, save the other one.

    Trick: after adding into the HashMap, we are looking for the 2nd index first.

        Always check (target - current) from the HashMap.

        If exist, that means index0 has already been pushed into the HashMap and current value is at index1.

    (key, value) = (numbers[i], i)

    Note: return index+1 because this is not 0-based.

*/

class Solution1 {

    public int[] twoSum(int[] nums, int target) {

        int[] rst = new int[2];

        if (nums == null || nums.length <= 1) return rst;

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            if (map.containsKey(target - nums[i])) {

                rst[0] = map.get(target - nums[i]);

                rst[1] = i;

                break;

            }

            map.put(nums[i], i);

        }

        return rst;

    }

}