Modified 3Sum Solution to Solve 3SumClosest Problem.


  • 0
    X

    Same idea as 3Sum. Just use minDist to keep track of the temporary closest distance, and a result to keep the result. You can't use (target-minDist) because you dont know the sign.

    public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = 0, minDist = Integer.MAX_VALUE;
        for(int i = 0 ; i < nums.length-2;){
            int j = i + 1, k = nums.length-1;
            while(j<k){
                int sum = nums[i]+nums[j]+nums[k];
                if(Math.abs(sum-target)<minDist){
                    minDist = Math.abs(sum-target);
                    result = sum;
                }
                if(sum < target){
                    j++;
                    while(nums[j] == nums[j-1] && j < k) j++;
                } else if(sum >target){
                    k--;
                    while(nums[k] == nums[k+1] && j<k) k--;
                } else return target;
            }
            i++;
            while(nums[i] == nums[i-1] && i < nums.length-2) i++;
        }
        return result;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.