1. 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, 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].

Solution:

When we see a number nums[i] in the input array, we want to check if target - nums[i] is also in the input array such that the sum of these two is target.


So, when we go through the input array, we maintains a HashMap that records the numbers we have already seen, and their indices. To check if a number is in the HashMap takes constant time.

If we found a match, we can return. Otherwise, we add the current number with its index to the HashMap.

Since we go through the input array only once, the time complexity is O(n).
The space complexity is O(n) because we use HashMap with extra space.



Code:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>01();
        for (int i = 0; i < nums.length; i++) {     
            if (map.containsKey(target - nums[i])) {
                return new int[] {map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[] {-1, -1};
    }
}