« Back
read.

Leetcode 16 3Sum Closest.

Leetcode 16 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

This question is a very good one, as you can use some way you already know and make some changes to fit this.

The key here is how to convert two pointer into three nums.


public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result=nums[0]+nums[1]+nums[2];
        Arrays.sort(nums);
        for(int i=0;i < nums.length-2;i++){
            int start=i+1;
            int end=nums.length-1;
            while(start < end){
                if(Math.abs(nums[i]+nums[start]+nums[end]-target) < Math.abs(result-target)){
                    result=nums[i]+nums[start]+nums[end];   
                }
                if(nums[i]+nums[start]+nums[end] < target){
                    start++;
                }else if(nums[i]+nums[start]+nums[end] > target){
                    end--;
                }else{
                    return target;
                }
            }
        }
        return result;
    }
}
comments powered by Disqus