32ms C++ easy to understand solution


  • 0
    K
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> res;
            if(nums.size()<4) return res;
            sort(nums.begin(),nums.end());
            vector<int> vec;
            for(int i=0; i<nums.size()-3; ++i) {
                for(int j=i+1; j<nums.size()-2; ++j) {
                    int sum = nums[i] + nums[j];
                    int start = j+1;
                    int end = nums.size()-1;
                    while(start<end) {
                        int sum2 = nums[start] + nums[end];
                        if(sum+sum2<target) {
                            start++;
                        } else if(sum+sum2>target) {
                            end--;
                        } else {
                            vec = {nums[i],nums[j],nums[start],nums[end]};
                            res.emplace_back(vec);
                            while (start<end && nums[start]==vec[2]) start++;
                            while (start<end && nums[end]==vec[3]) end--;
                        }
                    }
                     while (j+1<nums.size() && nums[j+1]==nums[j]) j++;
                }
                while (i+1<nums.size() && nums[i+1]==nums[i]) i++;
            }
            return res;
        }
    };
    

Log in to reply
 

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