Problem Explanation
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 has exactly one solution, and you may not use the same element twice. You can return the answer in any order.Example 1:
Input:nums = [2,7,11,15], target = 9
Output:[0, 1]
Explanation:Because nums[0] + nums[1] = 2 + 7 = 9
Example 2:
Input:nums = [3,2,4], target = 6
Output:[1, 2]
Explanation:Because nums[1] + nums[2] = 2 + 4 = 6
Example 3:
Input:nums = [3,3], target = 6
Output:[0, 1]
Explanation:Same value at different indices
Constraints:
- ◆
2 ≤ nums.length ≤ 10⁴ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹ - ◆
-10⁹ ≤ target ≤ 10⁹ - ◆
Only one valid answer exists
Approaches & Code
1
Brute Force
Time: O(n²)Space: O(1)🐢 Slow
💡 Approach
Check 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].
For each element at index i, loop through all elements after it at index j.
If nums[i] + nums[j] == target, return [i, j].
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[]{};
}
}
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
2
Optimal — Hash Map
Time: O(n)Space: O(n)⚡ Optimal
💡 Approach
Use 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.
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.
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int comp = target - nums[i];
if (map.containsKey(comp)) {
return new int[]{map.get(comp), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
}
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
comp = target - num
if comp in seen:
return [seen[comp], i]
seen[num] = i
return []
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int comp = target - nums[i];
if (map.count(comp)) {
return {map[comp], i};
}
map[nums[i]] = i;
}
return {};
}
Dry Run — Optimal Solution
Input:
nums = [2, 7, 11, 15], target = 9| i | nums[i] | complement | Map State | Action |
|---|---|---|---|---|
| 0 | 2 | 7 | {} | 7 not in map → add {2:0} |
| 1 | 7 | 2 | {2:0} | 2 IS in map → return [0, 1] |