Problem statement

Naive solution

The simple approach to solving this problem is to first iterate over the nums array. Then, for each integer in the nums array, iterate over all the integers in the nums array again, except the current integer, and check if the sum of the current integer and the other integer sums to target. When that occurs, return the corresponding indices.

Let $n$ be the length of the nums array. We will require $n$ iterations over the nums array, and for each iteration, we will require $n - 1$ more iterations over the nums array. In total, we will require $n(n-1) = n^2 - n$ iterations over the nums array, which translates to $O(n^2)$ time.

We do not use any space, so this solution requires $O(1)$ space.

Key insights

While iterating over a sequence, we can efficiently recall the values in the sequence that we iterated over by inserting these values as keys in a hash set or hash map, since these data structures allows $O(1)$ insertion and look-up.

In this case, we would like to use a hash map because we are interested not only in the values that we already iterated over, but also their corresponding index in the nums array.

This hash map allows us to avoid  $O(n)$  look-up for the values that we had already iterated over. That is, for each item in the sequence, we don’t need to iterate over the sequence up to, but not including, the current integer again to check what we had already iterated over. We can just check the contents of the hash map.

Alternatively, a hash set can be used instead if there are no values needed. In the case of this problem, the (key, value) pair is the integer that we iterated over and its corresponding index in the nums array.

Pseudocode

1. Initialize an empty hash map called Map.
2. For i = 0, ..., len(nums) - 1:
    a. Let diff = target - nums[i]
    b. If diff is a key in Map, let the value corresponding to this key be v.
    c. return [v, i].
    d. Otherwise, add nums[i] as a key to Map and let its corresponding value be i.

Notice that in step 2(d), we are essentially inverting the nums array. That is, the nums array takes in an index as an input and outputs the value at that index. The inverse of this is to take the value as input and output the corresponding index. So, the hash map Map is the inverse of the array nums.

Python code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i