Problem statement

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 has exactly one solution, and you may not use the same element twice.

Return the indices in ascending order.

Example 1

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

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: nums[1] + nums[2] == 2 + 4 == 6.

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: The same value may appear twice at different indices.

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one valid answer exists.

Follow-up: can you find an algorithm that runs in less than O(n^2) time?

Hints for Two Sum

1. Hint 1

   A brute force approach checks every pair — that is O(n²). Can you trade memory for speed?

2. Hint 2

   While scanning, ask: "have I already seen the number that completes this one?" A hash map from value → index answers that in O(1).

How to solve Two Sum

For each element the partner it needs is target - x. A hash map from value to index answers "have I seen the partner?" in O(1), so one pass finds the pair.

Approach

1. Walk the array with a map seen from value to index.
2. For element x at i, compute need = target - x; if need is in the map, return [seen[need], i].
3. Otherwise store seen[x] = i and continue.

Why it works

When the second member of the unique pair is reached, its partner was inserted earlier, so the lookup succeeds exactly once. Checking before inserting guarantees an element is never matched with itself, and the earlier index is naturally the smaller one.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Inserting before the lookup lets target = 2·x match x with itself.
• Sorting first finds a pair but loses the original indices.

Reference solution

Python

def twoSum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy