Two Sum

This is problem #3 in NeetCode's Arrays & Hashing section of problems.

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input: 
nums = [3,4,5,6], target = 7

Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10

Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10

Output: [0,1]

The code is stubbed out as follows:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

I didn't have a good idea of where to start with this one, so I started with a for-loop and just iterated over the nums array. I believe in my first attempt I came up with a solution that was O(n²). As usual, I could not come up with the actual insight on my own.

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

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen:
                return [seen[complement], i]
            seen[nums[i]] = i
        return []

The insight is that if we have a guarantee that two of the numbers add up to target, then it is necessarily the case the target - nums[i] exists in nums. The way we guarantee that i != j is by the fact that when we look for complement, we are only looking at values to the left of num[i], so any place where we find complement within nums will necessarily have an index less than i.