Practice › Hashing & Two Pointers
3Sum Closest
Medium · Hashing & Two Pointers · Asked at Amazon, Meta, Google, Microsoft
Choose three elements at different indices whose sum is closest to target, and print that sum. If two sums are equally close, print the smaller one.
Input
First line: n target. Second line: n integers.
Output
The closest sum.
Constraints
- 3 ≤ n ≤ 1000
- -1000 ≤ a[i] ≤ 1000
- -10^4 ≤ target ≤ 10^4
Sort, fix the first element, then move two pointers over the rest — O(n²).
Example 1
Input
4 1 -1 2 1 -4
Output
2
Example 2
Input
3 1 0 0 0
Output
0
Hints
- Sort the array. Fix the first element i, then look for the best pair in the part after i.
- With two pointers, if the current sum is below the target move the left pointer up, otherwise move the right pointer down. Update the best sum each time (smaller sum wins ties).
Approach
After sorting, for each i set l = i+1, r = n−1. The sum a[i] + a[l] + a[r] is compared with the best so far (closer distance wins; on equal distance keep the smaller sum). If the sum equals the target, it is optimal. If it is smaller, increasing l is the only way to get closer; if larger, decrease r. This explores every useful pair for each i in O(n).
Complexity: O(n²) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long t;
cin >> n >> t;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long best = a[0] + a[1] + a[2];
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
long long s = a[i] + a[l] + a[r];
long long ds = llabs(s - t), db = llabs(best - t);
if (ds < db || (ds == db && s < best)) best = s;
if (s < t) l++;
else if (s > t) r--;
else break;
}
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, t = data[0], data[1]
a = sorted(data[2 : 2 + n])
best = a[0] + a[1] + a[2]
for i in range(n - 2):
l, r = i + 1, n - 1
while l < r:
s = a[i] + a[l] + a[r]
if (abs(s - t), s) < (abs(best - t), best):
best = s
if s < t:
l += 1
elif s > t:
r -= 1
else:
break
print(best)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 t = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
Arrays.sort(a);
long best = a[0] + a[1] + a[2];
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
long s = a[i] + a[l] + a[r];
long ds = Math.abs(s - t), db = Math.abs(best - t);
if (ds < db || (ds == db && s < best)) best = s;
if (s < t) l++;
else if (s > t) r--;
else break;
}
}
System.out.println(best);
}
}