Share my AC C++ solution, around 50ms, O(N*N), with explanation and comments


  • 161
    K

    the key idea is the same as the TwoSum problem. When we fix the 1st number, the 2nd and 3rd number can be found following the same reasoning as TwoSum.

    The only difference is that, the TwoSum problem of LEETCODE has a unique solution. However, in ThreeSum, we have multiple duplicate solutions that can be found. Most of the OLE errors happened here because you could've ended up with a solution with so many duplicates.

    The naive solution for the duplicates will be using the STL methods like below :

    std::sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    

    But according to my submissions, this way will cause you double your time consuming almostly.

    A better approach is that, to jump over the number which has been scanned, no matter it is part of some solution or not.

    If the three numbers formed a solution, we can safely ignore all the duplicates of them.

    We can do this to all the three numbers such that we can remove the duplicates.

    Here's my AC C++ Code:

    vector<vector<int> > threeSum(vector<int> &num) {
        
        vector<vector<int> > res;
    
        std::sort(num.begin(), num.end());
    
        for (int i = 0; i < num.size(); i++) {
            
            int target = -num[i];
            int front = i + 1;
            int back = num.size() - 1;
    
            while (front < back) {
    
                int sum = num[front] + num[back];
                
                // Finding answer which start from number num[i]
                if (sum < target)
                    front++;
    
                else if (sum > target)
                    back--;
    
                else {
                    vector<int> triplet(3, 0);
                    triplet[0] = num[i];
                    triplet[1] = num[front];
                    triplet[2] = num[back];
                    res.push_back(triplet);
                    
                    // Processing duplicates of Number 2
                    // Rolling the front pointer to the next different number forwards
                    while (front < back && num[front] == triplet[1]) front++;
    
                    // Processing duplicates of Number 3
                    // Rolling the back pointer to the next different number backwards
                    while (front < back && num[back] == triplet[2]) rear--;
                }
                
            }
    
            // Processing duplicates of Number 1
            while (i + 1 < num.size() && num[i + 1] == num[i]) 
                i++;
    
        }
        
        return res;
        
    }

  • 0
    R
    This post is deleted!

  • 11
    R

    You should change rear to back


  • 0
    K

    Thank you for your comment. The rear word just came out of my mind before back at that time, and they have almost the same meaning. But anyway, thank you for pointing that out.


  • 0

    Very clear solution! Thanks for sharing.


  • 33
    C

    I had made it more faster by adding this piece of code to pruning your algorithm.

            if(target < 0)
            {
                break;
            }
    

    ^_^

    vector<vector<int> > threeSum(vector<int> &num) {
    
        vector<vector<int> > res;
    
        std::sort(num.begin(), num.end());
    
        for (int i = 0; i < num.size(); i++) {
    
            int target = -num[i];
            int front = i + 1;
            int back = num.size() - 1;
            
            if(target < 0)
            {
                break;
            }
    
            while (front < back) {
    
                int sum = num[front] + num[back];
    
                // Finding answer which start from number num[i]
                if (sum < target)
                    front++;
    
                else if (sum > target)
                    back--;
    
                else {
                    vector<int> triplet(3, 0);
                    triplet[0] = num[i];
                    triplet[1] = num[front];
                    triplet[2] = num[back];
                    res.push_back(triplet);
    
                    // Processing duplicates of Number 2
                    // Rolling the front pointer to the next different number forwards
                    while (front < back && num[front] == triplet[1]) front++;
    
                    // Processing duplicates of Number 3
                    // Rolling the back pointer to the next different number backwards
                    while (front < back && num[back] == triplet[2]) back--;
                }
    
            }
    
            // Processing duplicates of Number 1
            while (i + 1 < num.size() && num[i + 1] == num[i]) 
                i++;
    
        }
    
        return res;
    
    }

  • 0
    R

    I wonder why should'nt I put the removing duplicates of rear and front after the closed } of the else condition? why it should be inside else ? can you tell me why it is incorrect to put it after else?


  • 3
    V

    If we remove duplicates (as you mentioned in your "naive solution"), we will miss solution sets which include duplicates like {-2,-2,4}. Isn't it?
    Correct me if I am missing something.


  • 0
    L

    feels like we only need one of processing duplicates for Number 2 and 3. Since the value of num[i] is unchanged, it is ensured that,for the next solution, num[front](or num[back) will have different value if num[back](or num[front]) becomes different.


  • 5
    W

    Great! This is my solution based on yours with shorter code. Running a bit more faster:

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
    
        sort(nums.begin(), nums.end());
    
        for (auto i = 0; i < nums.size();) {
            auto target = -nums[i];
            int l = i + 1, u = nums.size() - 1;
    
            while (l < u) {
                auto sum = nums[l] + nums[u];
    
                if (sum < target)
                    while (nums[++l] == nums[l - 1]);  // Processing duplicates of Number 2
                else if (sum > target)
                    while (nums[--u] == nums[u + 1]);  // Processing duplicates of Number 3
                else {
                    result.push_back(vector<int>{nums[i], nums[l], nums[u]});
                    while (nums[++l] == nums[l - 1]);  // Processing duplicates of Number 2
                    while (nums[--u] == nums[u + 1]);  // Processing duplicates of Number 3
                } 
    
            }
    
            // Processing duplicates of Number 1
            while (nums[++i] == nums[i - 1]);
        }
    
        return result;
    }

  • 0
    J

    you can also cut "num[back] < 0" search progress


  • 0
    S

    I don't understand -- why is target < 0 not a valid condition?

    Nevermind -- figured it out. If nums[i] is positive, there is no way for two larger numbers (due to sorting) to sum to this value.


  • 0
    S

    If changing "i < num.size()" in the first line of the FOR loop to "i < num.size()-2", the function will be wrong. Could you please tell me why this will happen? Thank you!


  • 0
    J

    For example,a sorted array a<b<c, the aim is -1a=b+c
    if the target -1
    a<0, then a>0. so b+c<0. But 0<a<b<c, so b+c<0 is impossible.


  • 1
    Z

    Because num.size() is unsigned integer type. If your input is [ ], num.size()-2 is a very large number (18446744073709551614), you will get runtime error at the FOR loop.


  • 4
    R

    here is my code based on your algorithm with some optimization .

    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;
                   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++;
                           while(l<r-1 && nums[r]==nums[r-1]) r--;
                           l++; r--;
                       }
                   }
            }
           
            return res;
        }

  • 0
    K

    @SGM nums.size() is unsigned long, and unsigned(0)-2 is not -2, you should replace nums.size()-2 with static_cast<int>(nums.size())-2


  • 0
    A

    As someone brand new to Leetcode, I don't get the O(N x N) complexity of this Solution. Is that because you disregard the complexity of Sorting?. As much I understand, the complexity should be O(N x N) for the two loops plus that of Sorting. Thank you.
    @kun3


  • 2

    @abbasfaisal O(N^2) > O(NlgN) and hence O(N^2 + NlgN) is simplified to O(N^2)


  • 0
    L

    @wfxr When the input is [0,0,0,0], you code will throws an exception caused by vector subscript out of range. LeetCode OJ will not throws this exception but Visual Studio 2017 will. This is my code based on your code can avoid this exception.

    std::vector<std::vector<int>> threeSum(std::vector<int>& nums)
    {
        std::vector<std::vector<int>> result;
    
        sort(nums.begin(), nums.end());
    
        for (auto i = 0; i < nums.size() - 2;)
        {
            auto target = -nums[i];
            int l = i + 1, u = nums.size() - 1;
    
            while (l < u)
            {
                auto sum = nums[l] + nums[u];
    
                if (sum < target)
                    while (++l < nums.size() && nums[l] == nums[l - 1]); // Add a judgement condition of the range of vector subscript
                else if (sum > target)
                    while (--u < nums.size() && nums[u] == nums[u + 1]); // Add a judgement condition of the range of vector subscript
                else
                {
                    result.push_back(std::vector<int>{nums[i], nums[l], nums[u]});
                    while (++l < nums.size() && nums[l] == nums[l - 1]); // Add a judgement condition of the range of vector subscript
                    while (--u < nums.size() && nums[u] == nums[u + 1]); // Add a judgement condition of the range of vector subscript
                }
            }
    
            // Add a judgement condition of the range of vector subscript
            while (++i < nums.size() && nums[i] == nums[i - 1]);
        }
    
        return result;
    }
    

    Some of my advice

    First, I think the for loop can be break when i = nums.size() - 2. Because , if i >= nums.size() - 2, the remaining amount of data is less than three. The remaining data can not constitute a complete triple. So we can break the loop when i < nums.size() - 2.

    Second, I think if target < 0, you can also break the for loop. Because if target < 0 means nums[i] > 0, so the number after this also greater than 0 (nums are sorted in ascending order). The sum of three positive numbers can not be equal to zero. So we can break the for loop when target < 0.

    This is the modified for loop code snippet.

        int target{};
        // Modify the entry conditions of this loop
        for (auto i = 0; i < nums.size() - 2 && (target = -nums[i]) >= 0;)
        {
            int l = i + 1, u = nums.size() - 1;
    
            while (l < u)
            {
                auto sum = nums[l] + nums[u];
            ....
    

Log in to reply
 

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