Two Sum
Solve this Problemnums and an integer target, return the indicesIndicesThe position of each element within the array, starting at 0 for the first element. of the two numbers that add up to target.
You may assume that each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ nums.length ≤ 10⁴ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹ - ◆
-10⁹ ≤ target ≤ 10⁹ - ◆
Only one valid answer exists
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int[] twoSum(int[] nums, int target) { |
| 3 | Map<Integer, Integer> map = new HashMap<>(); |
| 4 | for (int i = 0; i < nums.length; i++) { |
| 5 | int comp = target - nums[i]; |
| 6 | if (map.containsKey(comp)) { |
| 7 | return new int[]{map.get(comp), i}; |
| 8 | } |
| 9 | map.put(nums[i], i); |
| 10 | } |
| 11 | return new int[]{}; |
| 12 | } |
| 13 | } |
| 14 |
05We're at index 0. nums[0] = 5. Our hashmap is still empty — nothing stored yet.
Approach & Solutions
Brute Force
BruteCheck every pair of elements using two nested loops. For each element at index i, loop through all elements after it at index j. If nums[i] + nums[j] == target, return [i, j].
O(n²)O(1)1class Solution {
2 public int[] twoSum(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 for (int j = i + 1; j < nums.length; j++) {
5 if (nums[i] + nums[j] == target) {
6 return new int[]{i, j};
7 }
8 }
9 }
10 return new int[]{};
11 }
12}Better — Sort + Two Pointer
BetterPair each value with its original index, then sort those pairs by value. Walk two pointers inward from both ends of the sorted pairs: if the pair sums too low, move left forward to raise it; too high, move right backward to lower it; an exact match returns the original indices carried alongside each value. Faster than brute force and needs no extra hashmap, but the sort itself costs O(n log n) — more than the hashmap approach needs.
O(n log n)O(n)1class Solution {
2 public int[] twoSum(int[] nums, int target) {
3 int n = nums.length;
4 int[][] pairs = new int[n][2];
5 for (int i = 0; i < n; i++) {
6 pairs[i][0] = nums[i];
7 pairs[i][1] = i;
8 }
9 Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
10 int left = 0, right = n - 1;
11 while (left < right) {
12 int sum = pairs[left][0] + pairs[right][0];
13 if (sum == target) {
14 return new int[]{pairs[left][1], pairs[right][1]};
15 } else if (sum < target) {
16 left++;
17 } else {
18 right--;
19 }
20 }
21 return new int[]{};
22 }
23}Optimal — Hash Map
OptimalUse a hash map to store each number and its index as you iterate. For each number, calculate complement = target - nums[i]. If complement already exists in the map, return both indices immediately. Single pass — no nested loop needed.
O(n)O(n)1class Solution {
2 public int[] twoSum(int[] nums, int target) {
3 Map<Integer, Integer> map = new HashMap<>();
4 for (int i = 0; i < nums.length; i++) {
5 int comp = target - nums[i];
6 if (map.containsKey(comp)) {
7 return new int[]{map.get(comp), i};
8 }
9 map.put(nums[i], i);
10 }
11 return new int[]{};
12 }
13}