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.
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
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9Only one valid answer exists.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?
For each number, you need to know 'have I already seen its complement (target - num)?' — a hash set/map answers that in O(1).
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.
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)