2Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Approach1: Dictionnary or Map

The general key to this problem is to be aware that there will always be one pair of numbers that will satisfy the target value. If we assume that the list contains element (x1, x2, x3, xn), there will inevitably be a pair that exists such that xa + xb = target.

• We first create a Dictionnary d that will map all elements of the list to their respective index.

• We then notice that we're able to solve the problem in one pass as we change the equation above to xa = target - xb. Since we already know the target, as long as we maintain all previous numbers to our records as we iterate, we will be able to verify whether xa = target - xb or xb = target - xa. Either way, we will find a corresponding pair.

• We iterate over the elements of list num, we verify whehther the dictionnary contains the complement pair. If it does not contain it, we add the element as well as it's index to the dictionary otherwise if it does, we have found a pair of element which equals the target.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, n in enumerate(nums):
            c = target - n
            if c in d:
                return [d[c], i]
            d[n] = i
        return[]

Time: O(n) Space: O(n)

Approach: Java Version

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        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};
    }
}