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. The order of the returned indices does not matter.

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: Using a Hash Map (Dictionary)

This problem can be efficiently solved using a hash map (or dictionary in Python) to store numbers we've encountered along with their indices. This allows for O(1) average time complexity for lookups, leading to an overall O(n) solution.

  • Initialize a hash map: This map will store (number, index) pairs.
  • Iterate through the array: For each num at index:
    • Calculate the complement: Determine complement = target - num. This is the value we need to find to make a sum equal to target.
    • Check the hash map: If complement already exists as a key in our hash map, it means we've found the two numbers. Return the index stored for complement and the current index.
    • Add to hash map: If complement is not found, add the current num and its index to the hash map. This prepares the map for future numbers that might need num as their complement.

Code (Python)

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        # Create a dictionary to store number -> index mappings
        num_map = {}

        # Iterate through the array with both index and value
        for i, num in enumerate(nums):
            # Calculate the required complement
            complement = target - num

            # Check if the complement exists in our map
            if complement in num_map:
                # If it does, we found the pair. Return their indices.
                return [num_map[complement], i]

            # If complement not found, add the current number and its index to the map
            num_map[num] = i

        # The problem statement guarantees exactly one solution,
        # so this line should theoretically not be reached.
        return []