C++ solution , 8 ms beats 99.02%


  • -1
    C

    class Solution {
    public:
    int threeSumClosest(vector<int>& nums, int target) {
    const int n=nums.size();
    sort(nums.begin(),nums.end());
    if(nums[n-1]+nums[n-2]+nums[n-3]<=target) return nums[n-1]+nums[n-2]+nums[n-3];
    if(nums[0]+nums[1]+nums[2]>=target) return nums[0]+nums[1]+nums[2];
    int candidate;
    int diff=2147483647;
    for(int i=0;i<n-2;i++){
    if(i!=0 && nums[i]==nums[i-1]) continue;
    if(nums[i]+nums[n-1]+nums[n-2]<=target) {
    candidate=nums[i]+nums[n-1]+nums[n-2];
    diff=candidate-target;
    continue;
    }
    int target2=target-nums[i];
    int j=i+1;
    int k=n-1;
    while(j<k){
    const int sum2=nums[j]+nums[k];
    if(abs(sum2-target2)<abs(diff)){
    diff=sum2-target2;
    }
    if(sum2>target2) k--;
    else if(sum2<target2) j++;
    else return target;

                while(nums[j]==nums[j-1]) j++;
                while(nums[k]==nums[k+1]) k--;
            }
        }
        return target+diff;
    }
    

    };


Log in to reply
 

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