Practice › Arrays
Two Sum
Medium · Arrays · Asked at Amazon, Google, Microsoft, Adobe, Flipkart
Given an array of n integers and a target, find two different indices i < j such that a[i] + a[j] = target. Exactly one such pair exists.
Input
- First line:
n - Second line:
nintegers - Third line:
target
Output
Print i j (0-based, with i < j).
Constraints
- 2 ≤ n ≤ 10^5
- Use a hash map for an O(n) solution.
Example 1
Input
4 2 7 11 15 9
Output
0 1
Example 2
Input
3 3 2 4 6
Output
1 2
Hints
- For each a[j], the partner it needs is target − a[j].
- Store each value's index in a hash map as you go; check the map before inserting a[j].
Approach
Walk j from left to right. Before storing a[j], look up target − a[j] in a hash map of value → index. If it's there, that index i is earlier than j, so print i j. Checking before inserting keeps an element from pairing with itself.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long target;
cin >> target;
unordered_map<long long, int> seen;
for (int j = 0; j < n; j++) {
auto it = seen.find(target - a[j]);
if (it != seen.end()) {
cout << it->second << " " << j << "\n";
return 0;
}
if (!seen.count(a[j])) seen[a[j]] = j;
}
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = data[1 : n + 1]
target = data[n + 1]
seen = {}
for j, x in enumerate(a):
if target - x in seen:
print(seen[target - x], j)
break
seen.setdefault(x, j)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long target = sc.nextLong();
Map<Long, Integer> seen = new HashMap<>();
for (int j = 0; j < n; j++) {
Integer i = seen.get(target - a[j]);
if (i != null) {
System.out.println(i + " " + j);
return;
}
seen.putIfAbsent(a[j], j);
}
}
}