-
Notifications
You must be signed in to change notification settings - Fork 1
/
ThreeSumClosest.java
39 lines (35 loc) · 1.21 KB
/
ThreeSumClosest.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
package com.leetcode;
import java.util.Arrays;
public class ThreeSumClosest {
//https://leetcode.com/problems/3sum-closest/
//O(N*N) , alternative is fix p1 and p2 pointers and do binSearch for p3 closest to sum that worst case is O(N*N logN)
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
int result = 0;
for(int p1 = 0 ; p1 < n-2 ; p1++){
int rem = target - nums[p1];//remaining
int l = p1+1;
int r = n-1;
while(l<r){
int sum = nums[l] + nums[r];
int diff = rem - sum;
if(minDiff > Math.abs(diff)){
minDiff = Math.abs(diff);
result = nums[p1] + nums[l] + nums[r];
}
if(diff == 0) return target;
if(diff > 0){
l++;
}
if(diff < 0){
r--;
}
}
}
return result;
}
}
}