Problem Statement

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

You can return the answer in any order.

Example 1:

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

Example 2:
Input: nums = [3,2,4]
target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109 Only one valid answer exists.

Approach I (Brute Force)

For each element i iterate through the list to see if there exists an element j such that i+j=target

Solution I

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if i!=j and nums[i]+nums[j]==target:
                return [i,j]
    return []

Note: The condition i!=j is required because of the given condition that we cannot use same element twice

Complexity: Time complexity is O(N2) and space complexity is O(1)

Approach II (Using Hashmap)

  • We use the hashmap to store an element along with it’s index
  • Instead of seeing if every element has a pair which sums to the target
  • We iterate through the list to see target-element exists in the list

Solution I

def twoSum(nums, target):
    hashMap = {}

    for i,n in enumerate(nums):
        diff = target - n

        if nums[diff] in hashMap:
            return [hashMap[diff], i]
        hashMap[n] = i

    return []

Complexity: Time complexity is O(N) and space complexity is O(N)

Refrence