/
3SumClosest.java
43 lines (40 loc) · 1.78 KB
/
3SumClosest.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// https://leetcode.com/problems/3sum-closest/
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closest = 100000;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int rem = target - nums[i] - nums[j];
int ix = Arrays.binarySearch(nums, j + 1, nums.length, rem);
if (ix < 0) ix = -ix - 1;
if (ix == nums.length && ix - 1 > j) {
int sum = nums[i] + nums[j] + nums[ix - 1];
if (Math.abs(target - sum) < Math.abs(target - closest)) {
closest = sum;
}
} else if (ix < nums.length) {
if (ix - 1 > j) {
int diff1 = Math.abs(target - nums[i] - nums[j] - nums[ix - 1]);
int diff2 = Math.abs(target - nums[i] - nums[j] - nums[ix]);
if (diff1 < diff2) {
if (diff1 < Math.abs(target - closest)) {
closest = nums[i] + nums[j] + nums[ix - 1];
}
} else {
if (diff2 < Math.abs(target - closest)) {
closest = nums[i] + nums[j] + nums[ix];
}
}
} else if (ix - 1 == j) {
int sum = nums[i] + nums[j] + nums[ix];
if (Math.abs(target - sum) < Math.abs(target - closest)) {
closest = sum;
}
}
}
}
}
return closest;
}
}