Easy

Two Sum

002

Given an array of integers nums and an integer target, return the indices of the two distinct values whose sum is target. Exactly one solution exists. Return the smaller index first.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    7,
    11,
    15
  ],
  "target": 9
}

Output
[
  0,
  1
]

FUNCTION SHAPE

nums: intArraytarget: int→intArray

SOLUTION NOTE

We can brute force this in `O(n²)` time and `O(1)` space, checking the formula: nums[i] + nums[j] == target. However with the hash map approach, we store the index mapping which gives us the original index i.

Reveal reference solution +

pythonREFERENCE

def twoSum(self, nums: List[int], target: int) -> List[int]:
    index = {}
    for i in range(len(nums)):
        if target - nums[i] in index:
            return [index[target-nums[i]], i]
        index[nums[i]] = i
    return -1

TimeO(n)

SpaceO(n)

Open on LeetCode ↗