C++ Solution O(n^3) Easy to understand! Clean


  • 0
    class Solution
    {
    private:
        //the next nums[pos] without duplicate numbers
        int inext(vector<int>& nums, int pos)
        {
            while(pos + 1 < nums.size( ) && nums[pos] == nums[pos + 1])
            {
                ++pos;
            }
            return ++pos;
        }
        //the prior nums[pos] without duplicate numbers
        int ipre(vector<int>& nums, int pos)
        {
            while(pos > 0 && nums[pos] == nums[pos - 1])
            {
                --pos;
            }
            return --pos;
            
        }
    
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target)
        {
            if(nums.size( ) < 4)
            {
                return { };
            }
            sort(nums.begin( ), nums.end( ));
            vector<vector<int>> res;
            res.reverse(200);
            for(int i = 0; i < nums.size( ) - 3; i=inext(nums,i))
            {
                for(int j = i + 1; j < nums.size( ) - 2; j=inext(nums,j))
                {
                    int beg = j + 1;
                    int end = nums.size( ) - 1;
                    while(beg < end)
                    {
                        int sum = nums[i] + nums[j] + nums[beg] + nums[end];
                        if(sum == target)
                        {
                            res.push_back( { nums[i], nums[j], nums[beg], nums[end] } );
                            beg = inext(nums, beg);
                            end = ipre(nums, end);
                        }
                        else if(sum < target)
                        {
                            beg = inext(nums, beg);
                        }
                        else
                        {
                            end = ipre(nums, end);
                        }
                    }//while
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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