Given an array of integers and a target, return the indices of the two numbers that add up to the target.
You are given an array of integers nums and an integer target. Return the indices of the two numbers such that they 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.
The naive O(n²) approach is a double loop. The optimal O(n) approach is a single pass with a hash map that stores each value's index as you scan — for every new value v, check whether target - v is already in the map; if it is, you have your pair.
A three-step tour of how you get from the brute force to the O(n) solution, and how to run each version live.
Every pair, checked. The obvious first attempt walks two nested loops — for every index i, scan every j > i and check whether nums[i] + nums[j] == target. The instant you find a match, return [i, j].
Correct, but O(n²). Ten thousand elements is a hundred million comparisons; a laptop CPU can just about get through that before your patience runs out. The constraint says up to 10⁴, so we need a faster approach.
Every scan of the inner loop is asking the same question: "have I seen target - nums[i] yet?" A hash map turns that lookup into O(1). Now the outer loop is the only real work: single pass, constant-time lookups per element.
The trick is remembering what you've seen SO FAR — not the whole array. Walk left-to-right; before adding nums[i] to the map, ask whether its complement is already there. If it is, you have your pair — and because you walked in order, the earlier index is the map value.
Complexity: O(n) time, O(n) space. The space cost is the hash map — every element might land in it before you find the pair. You've traded a linear memory ceiling for a single-pass runtime.
The C++ solution above uses unordered_map for the same lookup. Java uses HashMap<Integer, Integer>. Same pattern; the container name is the only thing that changes.
Reflex to build: when the naive solution asks the same lookup question repeatedly, reach for a hash map before you reach for a second loop.
nums = [2, 7, 11, 15] target = 9
[0, 1]
nums = [3, 2, 4] target = 6
[1, 2]
nums = [3, 3] target = 6
[0, 1]
Runnable starter code. Click "Try in playground" to open pre-loaded with the test fixtures.
def two_sum(nums, target):
seen = {}
for i, v in enumerate(nums):
if target - v in seen:
return [seen[target - v], i]
seen[v] = i
nums = list(map(int, input().split()))
target = int(input())
print(*two_sum(nums, target))
import java.util.*;
public class Solution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
throw new IllegalArgumentException();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] parts = sc.nextLine().split(" ");
int[] nums = new int[parts.length];
for (int i = 0; i < parts.length; i++) nums[i] = Integer.parseInt(parts[i]);
int target = Integer.parseInt(sc.nextLine());
int[] r = twoSum(nums, target);
System.out.println(r[0] + " " + r[1]);
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string line; getline(cin, line);
stringstream ss(line);
vector<int> nums; int x; while (ss >> x) nums.push_back(x);
int target; cin >> target;
unordered_map<int,int> seen;
for (int i = 0; i < (int)nums.size(); ++i) {
int need = target - nums[i];
auto it = seen.find(need);
if (it != seen.end()) { cout << it->second << " " << i << "\n"; return 0; }
seen[nums[i]] = i;
}
}