Java 4ms Solution beats 99% inspired by 3 sum.


  • 1
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        if(nums[len-3]+nums[len-2]+nums[len-1]<=target) return nums[len-3]+nums[len-2]+nums[len-1];//short  cut
        if(nums[0] + nums[1] + nums[2]>=target) return nums[0] + nums[1] + nums[2];//short cut
        int closest = nums[0] + nums[1] + nums[len - 1];
        for(int s = 0;s<len - 2;s++){
            if(s!=0&&nums[s-1]==nums[s]) continue;
            if(nums[s]+nums[len-1]+nums[len-2]<target&&s<len-3){//short cut
                closest = Math.abs(closest-target)>target - (nums[s]+nums[len-1]+nums[len-2])?nums[s]+nums[len-1]+nums[len-2]:closest;
                continue;
            }
            if(nums[s]+nums[s+1]+nums[s+2]>target){//short cut
                closest = Math.abs(closest-target)>(nums[s]+nums[s+1]+nums[s+2])-target?nums[s]+nums[s+1]+nums[s+2]:closest;
                break;
            }
            int newTarget = target - nums[s];
            int m = s+1;
            int b = len - 1;
            while(m<b){
                while(m!=s+1&&nums[m-1]==nums[m]&&m+1<b)m++; //skip duplicates
                while(b!=len-1&&nums[b+1]==nums[b]&&b-1>m)b--; //skip duplicates
                if(nums[m]+nums[b]<newTarget){
                    closest = Math.abs(closest-target)>newTarget - nums[m] - nums[b]?nums[s]+nums[m]+nums[b]:closest;
                    m++;
                }
                else if(nums[m]+nums[b]>newTarget){
                    closest = Math.abs(closest-target)>nums[m] + nums[b] - newTarget?nums[s]+nums[m]+nums[b]:closest;
                    b--;
                }
                else{        
                    return target;
                }
                
            }
        }
        return closest;
    }
    

    From zhidou and amber723's suggestions, I have modified the code to handle the Integer overflow which is not tested in the test case. Now closest is initialized with nums[0] + nums[1] + nums[len - 1] rather than Integer.MAX_VALUE.


  • 2
    Z

    great idea. but one more thing it will fail when input is [2,-1,-1,-1,3] -1, because you set closest to MAX_VALUE at first. I have the same problem


  • 1
    A

    Maybe you can set
    int closest = nums[0] + nums[1] + nums[len - 1];
    instead of
    int closest = Integer.MAX_VALUE;


  • 0

    @zhidou said in Java 4ms Solution beats 99% inspired by 3 sum.:

    2,-1,-1,-1,3] -1

    Yea. I see. Thank you for the suggestion. I gotta see how to handle it now.


  • 0

    @amber723 said in Java 4ms Solution beats 99% inspired by 3 sum.:

    nums[0] + nums[1] + nums[len - 1];

    Thank you for the suggestion. It does work. And I think it can solve the problem which brought by the overflow of MAX_INT in general.


Log in to reply
 

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