Problem
Given an array of integers nums and an integer target, return the indices
of the two numbers whose sum is equal to target.
You may assume there is exactly one valid answer, and you cannot use the same element twice.
Mind Map
- Need two values that combine to
target. - For each number, calculate the missing value:
target - current. - If the missing value was already seen, the answer is ready.
- Otherwise, store the current number with its index for future checks.
Brute Force Approach
Compare every pair of numbers and return the pair whose sum matches the target. This is simple, but it repeats work because every number is checked against many other numbers.
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
Time complexity: O(n^2)
Space complexity: O(1)
Optimized Approach
Use a hash map to remember numbers already visited. For every current number, ask one question: "Have I already seen the value needed to complete the sum?"
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let index = 0; index < nums.length; index++) {
const current = nums[index];
const required = target - current;
if (seen.has(required)) {
return [seen.get(required)!, index];
}
seen.set(current, index);
}
return [];
}
Time complexity: O(n)
Space complexity: O(n)
Walkthrough
For nums = [2, 7, 11, 15] and target = 9:
- At
2, required value is7. Store2 -> 0. - At
7, required value is2. It exists in the map. - Return
[0, 1].
Edge Cases
- Duplicate values, such as
[3, 3]with target6. - Negative numbers, such as
[-1, -2, -3]. - A valid answer appearing near the end of the array.