C++ solution O(n^2) using sort


  • 61
    A

    Sort the vector and then no need to run O(N^3) algorithm as each index has a direction to move.

    The code starts from this formation.

    ----------------------------------------------------
    ^  ^                                               ^
    |  |                                               |
    |  +- second                                     third
    +-first
    

    if nums[first] + nums[second] + nums[third] is smaller than the target, we know we have to increase the sum. so only choice is moving the second index forward.

    ----------------------------------------------------
    ^    ^                                             ^
    |    |                                             |
    |    +- second                                   third
    +-first
    

    if the sum is bigger than the target, we know that we need to reduce the sum. so only choice is moving 'third' to backward. of course if the sum equals to target, we can immediately return the sum.

    ----------------------------------------------------
    ^    ^                                          ^
    |    |                                          |
    |    +- second                                third
    +-first
    

    when second and third cross, the round is done so start next round by moving 'first' and resetting second and third.

    ----------------------------------------------------
      ^    ^                                           ^
      |    |                                           |
      |    +- second                                 third
      +-first
    

    while doing this, collect the closest sum of each stage by calculating and comparing delta. Compare abs(target-newSum) and abs(target-closest). At the end of the process the three indexes will eventually be gathered at the end of the array.

    ----------------------------------------------------
                                             ^    ^    ^
                                             |    |    `- third
                                             |    +- second
                                             +-first
    

    if no exactly matching sum has been found so far, the value in closest will be the answer.

    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size() < 3) return 0;
        int closest = nums[0]+nums[1]+nums[2];
        sort(nums.begin(), nums.end());
        for(int first = 0 ; first < nums.size()-2 ; ++first) {
            if(first > 0 && nums[first] == nums[first-1]) continue;
            int second = first+1;
            int third = nums.size()-1;            
            while(second < third) {
                int curSum = nums[first]+nums[second]+nums[third];
                if(curSum == target) return curSum;
                if(abs(target-curSum)<abs(target-closest)) {
                    closest = curSum;
                }
                if(curSum > target) {
                    --third;
                } else {
                    ++second;
                }
            }
        }
        return closest;
    }

  • 0
    R

    can you please explain a bit why complexity is O(n^2)? thanks


  • 0
    D

    Why do you use sort?


  • 0
    A

    because you need to loop on N elements N times average


  • 0
    A

    without sorting you will never know left element is always smaller than or the same to the right one so you have to compare everywhere again which means N^2 x N


  • 0
    S
    This post is deleted!

  • 0
    R

    why closest initialized as
    int closest = v[0]+v[1]+ v[2];


  • 0
    J

    It's just initialized as the sum of any three numbers in the array. Because you will iterate all the combinations of three numbers in the array, if there is a combination whose sum is closer to the target, closest will be updated. Just make sure the initial value of closest is not closer than the possible closest result in the array.


  • 0
    T

    Can u explain line6
    if(first > 0 && nums[first] == nums[first-1]) continue;
    what does it mean?


  • 0
    J

    I believe it is used to jump over the duplicated combination


  • 2
    R

    here is my code which is just similar to the code for previous problem 3Sum . but here we don't need to take consideration of duplicates.

    threeSumClosest

    int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            int n=nums.size(),ans;
            int min=INT_MAX;
            for(int i=0;i<n-2;i++){
                   int l=i+1, r= n-1;
                   while(l<r){
                       int sum =nums[i]+nums[l]+nums[r];
                       if(abs(sum-target)<min){  // updating the sum if sum  so far. is closest to target
                          min=abs(sum-target);
                          ans=sum;
                       }
                       if(sum<target) l++;        //
                       else if(sum>target)r--;
                       else {
                           ans=sum;  // we have sum equal to target which is closest so no need to check further 
                           i=n-2;  // for breaking the outer for loop
                           break;  // for breaking current while loop
                       }
                   }
            }
            return ans;
        }
    

    threeSum

    vector<vector<int>> threeSum(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            int n=nums.size();
            vector<vector<int>> res;
            for(int i=0;i<n-2;i++){
                   if(i>0 && (nums[i]==nums[i-1]) )continue;   // to avoid duplicates
                   int l=i+1, r= n-1;
                   while(l<r){
                       int sum =nums[i]+nums[l]+nums[r];
                       
                       if(sum<0) l++;
                       else if(sum>0)r--;
                       else {
                           res.push_back(vector<int>{nums[i],nums[l],nums[r]});
                           while(l+1<r && nums[l]==nums[l+1])l++;    // to avoid duplicates
                           while(l<r-1 && nums[r]==nums[r-1]) r--;     // to avoid duplicates
                           l++; r--;
                       }
                   }
            }
           
            return res;
        }

  • 0
    C

    C# implementation based on asbear's idea

        private int ThreeSumClosest(int[] nums, int target)
        {
            if (nums.Length <= 3)
            {
                return nums.Aggregate((a, b) => a + b);
            }
    
            Array.Sort(nums);
    
            int n = nums.Length;
            int ans = nums[0] + nums[1] + nums[2];
    
            for (int i = 0; i < n - 2; i++)
            {
                int j = i + 1;
                int k = n - 1;
    
                while (j < k)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == target)
                    {
                        return sum;
                    }
    
                    if (Math.Abs(target - sum) < Math.Abs(target - ans))
                    {
                        ans = sum;
                    }
    
                    if (sum > target)
                    {
                        k--;
                    }
                    else
                    {
                        j++;
                    }
                }
            }
    
            return ans;
        }

  • 2
    T

    You could also add:

    int vsize = nums.size();
    int firstThree = nums[0] + nums[1] + nums[2];
    int lastThree = nums[vsize-1] + nums[vsize-2] + nums[vsize-3];
            
    if((target-firstThree) < 0 && (target-lastThree) < 0) return firstThree;
    if((target-firstThree) > 0 && (target-lastThree) > 0) return lastThree;
    

    at the top to make it faster, for a few specific cases.


  • 0
    C

    @timetraveler_0

    if(target < firstThree) return firstThree;
    if((target > lastThree) return lastThree;
    

    is enough.

    by the way, in the first for loop, add

    n = nums.size();
    int with_i_fixed_max = nums[i]+nums[n-1]+nums[n-2] ;
    if (with_i_fixed_max  < target && abs(with_i_fixed_max - target) < abs(target - closest) ) {
        closest = with_i_fixed_max;
        continue;
    }
    int with_i_fixed_min = nums[i]+nums[i+1]+nums[i+2]
    if (with_i_fixed_min > target && abs(with_i_fixed_min - target) < abs(target - closest) ) {
        closest = with_i_fixed_min;
        continue;
    }
    

    also helps for some special cases.


  • 0
    W
    This post is deleted!

  • 0
    C

    @ThreeRice Excpet the same number


  • 0
    S

    concise mind!!your explaination is very helpful !!


Log in to reply
 

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