Two Sum
Given an integer array nums and a target, return the two zero-based indices whose values add to the target. Exactly one pair exists, and the two indices must be different. The answer may list the indices in either order. There are between 2 and 10,000 values; both the values and the target lie between -10^9 and 10^9.
Start with pairs
For nums = [3, 2, 4] and target = 6, take the 3 at index 0 and check every later value. None makes 6. Take the 2 at index 1 and check the 4 at index 2: that pair works, so return [1, 2].
The direct method checks each pair once by choosing indices i < j. For n values, there are n * (n - 1) / 2 pairs, so this takes O(n²) time and O(1) extra space. At 10,000 values, it may inspect 49,995,000 pairs. The follow-up asks us to do better than quadratic time.
For a current value x, its partner has only one possible value: target - x. We can check every pair in the opposite order too: visit its later position and search the earlier positions for that partner. This still repeats a search through values we have already visited.
Look up the missing value
Keep a map from each earlier value to an index where it occurred. For example, after visiting 3 and 2 in [3, 2, 4], the map contains 3 -> 0 and 2 -> 1. The current value 4 needs 6 - 4 = 2; looking up 2 gives index 1 immediately. A hash map supports this lookup in expected constant time.
Walk left to right. At index i, first look up target - nums[i]. If it is present, the map gives an earlier index and i gives the current one. If it is absent, save nums[i] -> i and keep going.
Keep the indices distinct
With [3, 3] and target 6, the first 3 has no earlier partner, so save index 0. The second 3 finds it and returns [0, 1]. If the current value were saved before the lookup, the first 3 would match itself and return the invalid answer [0, 0].
At every lookup, the map contains one index for each distinct value at positions before i. Saving a repeated value can replace its stored index; either earlier occurrence works when a later value needs that complement.
Why a pair is found
If a lookup finds a match, its value is target - nums[i], so the two values sum to the target. Its index is strictly before i, which gives two distinct positions. To see why a pair cannot be missed, take its later position: by then, the earlier value is already in the map. The problem guarantees a solution, so the loop returns a valid pair before reaching the end.
Implementation
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index_by_value = {}
for current_index, current_value in enumerate(nums):
needed_value = target - current_value
if needed_value in index_by_value:
earlier_index = index_by_value[needed_value]
return [earlier_index, current_index]
index_by_value[current_value] = current_index
return []Complexity
For n = len(nums), the loop makes a constant number of map accesses per value. Each takes expected time, so the expected total is time and the map uses extra space. A hash table can take for an individual operation under heavy collisions, so the theoretical worst-case time is .