Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Constraints:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution

Approach: Hash Map (Dictionary)

This problem can be efficiently solved using a hash map (or dictionary in Python) to store numbers and their corresponding indices as we iterate through the array.

Steps:

  • Initialize an empty hash map, let's call it num_map, to store (number: index) pairs.
  • Iterate through the nums array using both the index i and the value num.
  • For each num, calculate the complement needed to reach the target: complement = target - num.
  • Check if this complement already exists as a key in num_map.
    • If it exists, it means we have found the two numbers. The current number num at index i and the complement found at num_map[complement] are our pair. Return [num_map[complement], i].
    • If it does not exist, add the current num and its index i to num_map: num_map[num] = i.
  • Since the problem statement guarantees exactly one solution, we will always find a pair and return from inside the loop.

Time Complexity: O(N)

  • We iterate through the list once. Each lookup and insertion into the hash map takes O(1) on average.

Space Complexity: O(N)

  • In the worst case, the hash map might store all elements from the nums array.

Python Solution:

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i
        return [] # Should not reach here based on problem constraints