For each number we encounter, we need to find if its complement (target - num) exists in the array. Instead of searching the entire array each time (O(n²)), we can store previously seen numbers and check if the current number completes any previous pair.

We use a hash map to store the complements we're looking for as we iterate through the array. For each number:

1. Check if it exists as a key in our hash map (meaning it's the complement of a previous number)

2. If yes, we've found our pair—return both indices

3. If no, store the complement we need (target - current number) with the current index

This works because we only need to check backwards—if the complement existed earlier, we would have already found it.

Time complexity: O(n)

Single pass through the array

Hash map lookup and insertion are O(1) average case

Space complexity: O(n)

Worst case: store n-1 entries in the hash map (when the answer is the last pair)

class Solution:

    def twoSum(self, nums: List[int], target: int) → List[int]:

        len_nums: int = len(nums)

        remaining_values: dict[int, int] = {} # value as index of j, looking for i which matches a key

        for i in range(len_nums):

            num = nums[i]