L1 Two Sum

HashSet and Brute Force

Problem

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

• one pass hash map TC:O(n) SC:O(n)

Since map stores all the numbers, if we could find one of the res, the other one will be target - res.

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

• Brute Force TC:O(n^2) SC: O(1)

public int[] twoSum(int[] nums, int target){
  
    for(int i = 0; i < nums.length; i++){
        for(int j = 0; j < nums.length; j++){
            if(nums[j] == target - nums[i])
        }
        return new int[]{i,j};
    }
}