Java solution with O(n2) for reference


  • 76
    C

    Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element. If the sum is less than target, it means we have to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating.

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

  • 10
    L

    I think it would be better to break early when sum==target.


  • 4
    L

    it is better that you should check if the num array length is less equal than 3 elements, then return their sum.

        if (num.length <= 3) {
            for (int i: num) {
                sum += i;
            }
            return sum;
        }
    

  • 0
    W

    Agreed~~~~~~~~~~~~


  • 0

    Well, this case has been included implicitly in the logic of the above code and may make the code unclean if written down explicitly :-)


  • 1
    Z

    Why is this case included? For example, if there is only element in nums, the solution in this thread throws an exception because of nums[1].


  • 15
    M

    You answer is great. However, we could improve performance a bit by skipping duplicate elements.

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int sum = nums[0] + nums[1] + nums[nums.length - 1];
        int closestSum = sum;
        
        for(int i = 0; i < nums.length - 2; i++){
            if(i==0 || nums[i]!=nums[i-1]){
                int left = i + 1, right = nums.length - 1;
                while(left < right){
                    sum = nums[left] + nums[right] + nums[i];
                    if(sum < target){
                        //move closer to target sum.
                        while(left<right && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                    }else if(sum > target){
                        //move closer to target sum.
                        while(left<right && nums[right] == nums[right-1]){
                            right--;
                        }
                        right--;
                    }else{
                        return sum;
                    }
                    //update the closest sum if needed.
                    if(Math.abs(target - sum) < Math.abs(target - closestSum)){
                        closestSum = sum;
                    }
                }
            }
    
        }
        return closestSum;
    }

  • 0
    Z

    look at this --> for(int i = 0; i < nums.length - 2; i++)


  • 0
    S

    Great solution, any further comment on how to generalize the approach? thanks a lot!


  • 0
    F

    could anyone tell me what the problem is in my solution? actually i just change one line of your solution

    public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int result = nums[0]+nums[1]+nums[nums.length-1];
    for(int i = 0; i < nums.length -2 ; i ++){
    int low = i + 1, high = nums.length-1;
    while(low < high){
    int sum = nums[i]+nums[low]+nums[high];
    if(sum<target)
    low++;
    else if(sum>target)
    high--;
    else
    return target;
    result = Math.abs(sum-target)<Math.abs(result-target)?sum:result;
    }
    }
    return result;
    }

    when i run the test case I can get the correct result. However when i summit my solution it will show Time Limit Exceeded


  • 0
    H

    I think it is better to skip the same value:)
    public int threeSumClosest(int[] nums, int target) {
    int ret = nums[0] + nums[1] + nums[2];

        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
        	
        	while (i > 0 && i < nums.length && nums[i] == nums[i-1])
    			i++;
        	int j=i+1;
        	int k=nums.length-1;
        	
        	while(j<k){
        		int sum = nums[i] + nums[j] + nums[k];
    
        		if(sum==target){
        			ret = sum;
        			return sum;
        		}
        		
        		if(Math.abs(sum-target) <= Math.abs(ret-target)){
        			ret = sum;
        		}
        		
        		if(sum > target){
    			k--;
    			while(j < k &&nums[k] == nums[k+1])
    				k--;
        		}else{
        			j++;
    			while( j < k && nums[j] == nums[j-1])
    				j++;			
        		}
    
        	}
        }
    
        return ret;

  • 0
    C

    I have to say that the solution is wrong seriously.
    We can assume a testcase like 0,1,2,5,9 and the target is 9, so we choose 0,1,9 as the first three numbers, the sum is bigger than 9 but 10-9=1,it's pretty small. However, the next step is move the right point to 5, so the number is 0+1+5=6, and next step is 0+2+5=7, then stop and i moves to the next place. What happened? we miss the closest number when i=0, so we miss the closest sum whatever i is.
    If your answer passed the test, I have to say there are some problems with the design of testcases


  • 0
    G

    @cheyasa said in Java solution with O(n2) for reference:

    all. However, the next step is mov

    when 'sum = 6', |6 - 9| > |10 - 9|. So, it won't update the result.


  • 0
    R

    wonderful---thank for your help


  • 0
    X

    @chase1991

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

            }
        }
        return result;
    }
    

    '


  • 0
    X

    @xinghongfei

    ' if (Math.abs(sum - target) < Math.abs(result - target)) {
    result = sum;
    }'


  • 0
    X

    @xinghongfei

    '
    if (Math.abs(sum - target) < Math.abs(result - target)) {
    result = sum;
    }

    '


  • 0
    X

    @xinghongfei

       if (Math.abs(sum - target) < Math.abs(result - target)) {
                    result = sum;
                }

  • 0
    X

    @chase1991

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

        }
    }
    return result;
    

    }


  • 0
    G

    @FreeLance said in Java solution with O(n2) for reference:

    public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int result = nums[0]+nums[1]+nums[nums.length-1];
    for(int i = 0; i < nums.length -2 ; i ++){
    int low = i + 1, high = nums.length-1;
    while(low < high){
    int sum = nums[i]+nums[low]+nums[high];
    if(sum<target)
    low++;
    else if(sum>target)
    high--;
    else
    return target;
    result = Math.abs(sum-target)<Math.abs(result-target)?sum:result;
    }
    }
    return result;
    }

    i summit your solution ,and the server accept the code.so what happened to you?


Log in to reply
 

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