Two Sum

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.

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

Approach

Scan the array while keeping a hash map from value to its index. For each number, compute the complement target - num and check if it has been seen; if so, return the stored index and the current index. This naturally handles duplicates and negative values, and returns indices in increasing order because the stored index is always from an earlier position.

Why It Works

At any position i), the map contains exactly the indices of all earlier elements. If nums[i]completes a valid pair with some earliernums[j], then the complement lookup finds jand we return[j, i]`. The problem guarantees exactly one solution, so the first such match is correct.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

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