───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

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.

Solution

Two loops work, but slow (O(n^2)).
Instead, solve with a hashmap that has the seen numbers (O(n)) as a key, and the index as a value.
- Then, we loop and check if the complement of n exists in the hashmap. If so, return the two indices.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # time complexity: O(n)
        # space complexity: O(n)
        seen = {}
 
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
 
            seen[num] = i
 
        return []

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───