Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume that each input has exactly one solution, and you may not use the same element twice.

This is a classic array-based problem that teaches efficient searching using hash maps and is commonly asked in coding interviews.

Example

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1] (because nums[0] + nums[1] == 9)

Input: nums = [3, 2, 4], target = 6

Output: [1, 2]

Code

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return new int[0]; // just in case
    }
}
            

def two_sum(nums, target):
    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

# Example usage
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]
            

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

// Example usage
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]
            

Explanation

• Iterate through array: For each number, calculate the complement needed to reach the target.
• Use hash map: Store numbers and their indices as you iterate.
• Check as you go: If the complement already exists in the map, return the current index and the stored index.
• Why this works: The map allows O(1) lookup time, reducing overall complexity.

Note