Two Sum — Editorial

Opening the reading…

Intuitioneach number tells you exactly what must have appeared before it

For a value x at index i to belong to the answer, its partner is not arbitrary: it must equal target - x. The problem therefore becomes a search for one earlier value while scanning the array. If that partner has already appeared, its stored index and i form the answer immediately.

Store each value together with its index as you pass it. The order matters: look for target - nums[i] before storing nums[i] itself. That guarantees the stored partner comes from a different index, so the current element can never be matched with itself. The unique-answer guarantee means the first match is enough.

Approachone lookup and one insertion per element

Create a hash map from a value to its index, because checking every earlier value would repeat work and lead to quadratic time.

Scan nums from left to right, keeping the current index i so the returned pair contains positions rather than only values.

Compute need = target - nums[i], because only this complementary value can combine with nums[i] to reach target.

Look up need before inserting the current value, because inserting first could let nums[i] match itself when need equals nums[i].

If need is already in the map, return its stored index and i; the two indices are distinct because the current element has not been stored yet.

If no match exists, store nums[i] with index i so a later element can use it as its earlier partner.

Return an empty vector only as a fallback after the scan; the problem guarantees that a valid pair exists.

Complexityexpected bounds from constant-time hash operations

MEASURE	BOUND	WHY
Time	O(n) expected	Each index is processed once, with one expected constant-time lookup and at most one expected constant-time insertion. The scan stops at the match, so it never does more than n iterations; pathological hash collisions can degrade this to O(n^2).
Space	O(n) extra	The map stores at most one entry per scanned element, and the returned two-index vector is required output excluded from working-space usage. In the worst shape, the matching pair is at the end, so nearly all n values remain stored.

Here n is the number of elements in nums. The hash map's stated lookup and insertion costs are expected bounds.

Annotated solutionC++ · one pass with a value-to-index hash map

CPPOne left-to-right pass that checks the complement before recording the current value.

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    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];
            auto it = seen.find(need);

            if (it != seen.end()) {
                return {it->second, i};
            }

            seen[nums[i]] = i;
        }

        return {};
    }
};

The two key lines are the lookup and the insertion order. At index i, find the complement among earlier elements first. Only when it is absent do you record the current value. This handles duplicates naturally: for [3, 3] with target 6, the first 3 is stored and the second 3 finds it, producing two different indices.