Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given an array of integers `nums` and an integer `target`, return the indices of the two numbers that add up to `target`.
Constraints & assumptions
- 2 ≤ nums.length ≤ 10⁴
- −10⁹ ≤ nums[i] ≤ 10⁹
- −10⁹ ≤ target ≤ 10⁹
- Exactly one valid answer exists
- You may not use the same element twice
In plain English
Imagine a party with a deal: any two guests whose ages add up to a magic number get in free. The slow way is to compare every guest with every other guest — exhausting. The clever way: stand at the door with a notepad. As each guest arrives, you ask a single question — "who do I still need to make the magic number?" — and glance at your notepad to see if that person already arrived.
That instant "have I seen this already?" glance is exactly what a hash map gives you. You trade a little memory (the notepad) for a huge amount of speed, turning a slow pairwise search into a single walk down the line.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1The brute-force idea: try every pair (i, j) and check if they sum to the target.
- 2To speed it up, scan the array once and remember every number you've already seen along with its index.
- 3For the current number x, compute the complement you need: target − x.
- 4If that complement is already in your map, you've found the pair — return both indices.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Check every pair. Simple to write, but quadratic time.
Two nested loops try every combination of indices. It's correct and needs no extra memory, but it re-examines the same numbers again and again, which is slow for large inputs.
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] { i, j };
}
}
}
return new int[] {}; // no valid pair (won't happen per constraints)
}
}