My c++ solution


  • 0
    B
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int> > result;
            int n = nums.size();
            if (n < 4)
            {
                return result;
            }
        
            sort(nums.begin(), nums.end());
    
            int i = 0;
            while (i < n)
            {
                if (i > 0 && nums[i] == nums[i-1])
                {
                    i++;
                    continue;
                }
                int j = i+1;
                while (j < n)
                {
                    if (j > i+1 && nums[j] == nums[j-1])
                    {
                        j++;
                        continue;
                    }
    
                    int sum = target - nums[i] - nums[j];
                    int left = j+1;
                    int right = n-1;
                    while (left < right)
                    {
                        int value = nums[left] + nums[right];
                        if (sum == value)
                        {
                            vector<int> temp;
                            temp.push_back(nums[i]);
                            temp.push_back(nums[j]);
                            temp.push_back(nums[left]);
                            temp.push_back(nums[right]);
    
                            result.push_back(temp);
                            left++;
                            while (left < right && nums[left] == nums[left-1])
                            {
                                left++;
                            }
                        }
                        else if (value > sum)
                        {
                            right--;
                            while (right > left && nums[right] == nums[right+1])
                            {
                                right--;
                            }
                        }
                        else
                        {
                            left++;
                            while (left < right && nums[left] == nums[left-1])
                            {
                                left++;
                            }
                        }
                    }
                    j++;
                }
                i++;
            }
    
            return result;
        }
    };

Log in to reply
 

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