Sharing my Java Optimized solution 5ms, beats 99.9%


  • 5
    L

    It is just some optimized work after basic 3Sum structure.

    public int threeSumClosest(int[] nums, int target) {
        if(nums.length<3) return 0;
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;int result =Integer.MAX_VALUE;
        for(int i=0;i<nums.length-2;i++)
        {
            if(3*nums[i]>target) 
            {
                int sum3 = nums[i]+nums[i+1]+nums[i+2];
                if(Math.abs(sum3-target)<min)  return sum3;
                //break;           //should break here but seems slower after adding it
            }
            int left = i+1; 
            int right = nums.length-1;
            int sum = target - nums[i];
            if(2*nums[right]<sum) {
                int sum2 = nums[i]+nums[right]+nums[right-1];
                 if(Math.abs(sum2-target)<min){
                     min = Math.abs(target-sum2);
                     result = sum2;
                 }
               continue;
            }
            while(left<right)
            {
                int temp = nums[i] + nums[left]+nums[right];
                if(temp==target) return target;
                if(2*nums[left]>sum) 
                {
                  int sumsum = nums[i]+nums[left]+nums[left+1];
                  if(Math.abs(sumsum-target)<min){
                      min = Math.abs(target-sumsum);
                      result = sumsum;
                    }
                   break;
                }
                else if(Math.abs(target-temp)<min)
                {
                    min = Math.abs(target-temp);
                    result = temp;
                }
                if(temp<target) 
                   left++;
                else right --;
            }
        }
        return result;
        }

  • 0
    B

    try the case 1,8,8,8,9,9 and target = 20, this will get wrong answer 17.
    The key is in your second prune.
    sum2 = nums[i] + nums[right-1] + nums[right]


  • 0
    L

    I think your optimazation is brova!!
    but in this part,I think it needs a "break;" in the end. Otherwise, if it didn't return, it would still run the rest code, which is useless, and there is no need to try another i.

    if(3*nums[i]>target) {                 
        int sum3 = nums[i]+nums[i+1]+nums[i+2];
        if(Math.abs(sum3-target)<min)  
            return sum3;
    }
    

  • 0
    L

    Nice one! I have updated it


  • 0
    L

    you are right, but looks slower after I add it


  • 0
    8

    @baobaohanhan actually the result is 19


Log in to reply
 

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