Two Sum
Problem
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 that each input would have exactly one solution, and you may not use the same element twice.
Examples
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9
Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: nums[1] + nums[2] == 6
Constraints
- •
2 <= nums.length <= 10^4 - •
-10^9 <= nums[i] <= 10^9 - •
Only one valid answer exists.
Hints
Hint 1
The brute force checks every pair of numbers directly — O(n^2). What single piece of information, looked up in O(1), would let you avoid re-scanning the array for each element?
Hint 2
For each number, you need to know 'have I already seen its complement (target - num)?' — a hash set/map answers that in O(1).
Hint 3
Store each number's INDEX (not just whether you've seen it) as you go, so you can return both indices the moment you find a match.
Solutions
public int[] twoSumBruteForce(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};
}
}
}
throw new IllegalArgumentException("No solution");
}Time: O(n^2) · Space: O(1)