coding-Interview/ThreeSumClosest.java at master · arjunmullick/coding-Interview · GitHub

39 lines (35 loc) · 1.21 KB

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;

}

Expand file tree