Two Sum

Problem

Given an array nums and a target, return the indices of the two numbers that add up to target. Each input has exactly one solution.

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

Python Solution

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

C++ Solution

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

Java Solution

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

Complexity

Time: O(n) — each element is checked against the hash map once, with O(1) average lookup. Space: O(n) — the hash map can hold up to n values seen so far.