Java O(n^2) solution using sort


  • 0
    M
    public class Solution {
        public int threeSumClosest(int[] nums, int target) {
            if(nums==null || nums.length<3) return 0;
            final int n = nums.length;
            Arrays.sort(nums);
            int end=n-1, sum = nums[0]+nums[1]+nums[end], 
            	min=Integer.MAX_VALUE, dif = min, abs = min, ans = min;
            while(end>2 && sum>target){
                end--;
                sum = nums[0]+nums[1]+nums[end];
            }
            if(sum==target) return sum;
            if(end<n-1) end++;
            int l=0, m=1, r=end;
            for(; l<=end-2; l++){
                m=l+1; r = end;
                while(m<r){
                    sum = nums[l]+nums[m]+nums[r];
                    dif = sum-target;
                    if(dif==0) return sum; //sum==target
                    if(dif>0){//sum>target
                    	abs = dif;
                        r--;
                    } else { //sum<target
                        abs = -dif;
                        m++;
                    }
                    if(min>abs){
                    	min = abs;
                    	ans = dif;
                    }
                }
            }
            return target+ans;
        }
    }
    

Log in to reply
 

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