Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.
You may assume each input has exactly one solution, and you may not use the same element twice. You can return the two indices in any order.
x, the partner you need is exactly target - x. If you've already met that partner, you're done.O(1) instead of a scan.target - x as you go.Input: nums = [2,7,11,15], target = 9 Output: [0,1] Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6 Output: [1,2] nums[1] + nums[2] == 6.
Input: nums = [3,3], target = 6 Output: [0,1] The two 3s live at indices 0 and 1.
- 2 <= nums.length <= 10^4 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9 - Only one valid answer exists.
Two Sum is the classic find a pair that sums to a target problem, and the gateway to a whole family of pair-and-complement problems. The brute force is obvious; the optimal turns on a single idea — remember what you've seen — that reappears in 3Sum, subarray sums, and beyond. Work through it in layers, then read the full code in the Approaches below.
O(1) average lookup and insert. The one data structure that makes this problem linear.O(n²) scan over 10⁴ items (~10⁸ steps) is risky, while a single O(n) pass is comfortable.Formally: given nums and a target, return the indices i and j (with i != j) such that nums[i] + nums[j] == target. Exactly one such pair exists, and the two indices may come back in any order.
Worked example — nums = [2, 7, 11, 15], target = 9
nums = [2, 7, 11, 15] target = 9
▲ ▲
2 + 7 = 9 → answer: indices [0, 1]
Two minutes of sharp questions before coding signals seniority and surfaces edge cases that change your approach.
“Is exactly one valid answer guaranteed?”
If not, you'd need to handle the no-solution and multiple-solution cases, which is a different contract.
“Can I use the same element twice?”
No, so the algorithm must avoid pairing an index with itself.
“Can the array contain duplicate values?”
Yes — nums = [3, 3] is valid. Identical values can sit at different indices, and the pair may be two of them.
“Can values be negative or zero?”
Yes. The complement logic is identical, so never assume positives.
“Do I return the indices or the values?”
The indices, meaning positions rather than numbers. Worth confirming, since it rules out anything that reorders the array.
“Does the order of the two indices matter?”
No, any order is accepted.
“What is the maximum array length?”
Up to 10⁴. An O(n²) scan runs ~10⁸ operations, borderline for the time limit, which nudges you toward an O(n) approach.
Before I start, a couple of quick questions.
Should I return the two indices, or the values themselves?
Is exactly one solution guaranteed, or could there be none, or several?
Can the same element be used twice?
Great. With those settled, I'll start from the obvious check-every-pair approach, then look for something faster.
Brute force treats this as two-dimensional: for every i, try every j. But once you fix the first number x, the second is not a choice — it must be exactly target - x. The real question collapses to one dimension: "have I already seen the value target - x?"
"Have I seen this value, and where?" is exactly what a hash map of value → index answers instantly. Walk the array once and, for each element, look up its complement. That turns the O(n²) pair scan into a single O(n) pass.
Look up the complement of the current element before you store it. Skip that ordering and, when target is even, an element equal to target / 2 finds itself in the map and returns [i, i], an illegal self-pair. Getting the two steps in the right order is the whole trick.
| Brute force | Hash map | |
|---|---|---|
| Idea | Try every pair (i, j) | Look up each complement once |
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
| n = 10⁴ | ~10⁸ ops (risky) | ~10⁴ ops |
The full code for both, with dry runs and the pitfalls to avoid, is in the Approaches selector below.
Key takeaway
The complement trick: turn "find two numbers that sum to T" into "for each x, has its complement T − x already been seen?" A hash map makes that lookup O(1), so one pass over the array replaces the O(n²) search — O(n) time for O(n) space.