Two Sum

Intuition

The most direct idea is to simply examine each possible combination of two entries. For every element we look at all the elements that come after it, add the two together, and check whether the total matches the target. Since the problem guarantees a unique answer, the first matching pair we find is the one to return.

Algorithm walkthrough

1. 1Walk an outer index `i` across the array from the first element to the last.
2. 2For each `i`, walk an inner index `j` starting just after `i` to the end of the array.
3. 3Compare the sum of `nums[i]` and `nums[j]` against `target`.
4. 4As soon as the sum equals `target`, return the pair `[i, j]`.

Implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

Intuition

For any element `x`, the partner we need is `target - x`, its complement. Instead of searching for that complement with a second loop, we remember every value we have already seen in a hash map that maps a value to its index. As we pass over each element we ask the map whether its complement has shown up earlier; if it has, we have found the pair in a single scan.

Algorithm walkthrough

1. 1Create an empty hash map that associates each value with the index where it appeared.
2. 2Iterate through the array once, and for the current element `x` compute `target - x`.
3. 3If that complement is already a key in the map, return the stored index paired with the current index.
4. 4Otherwise, record `x` and its index in the map and continue to the next element.

Implementation

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