Share my concise C++ solution 80ms


  • 0
    M
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> result;
            if (nums.size() < 4) {
                return result;
            }
            sort(nums.begin(),nums.end());
            for (int i = 0; i < nums.size()-3; i++) {
                for (int j = i+1; j < nums.size()-2; j++) {
                    int left = j + 1, right = nums.size()-1, newTarget = target - (nums[i]+nums[j]);
                    while (left < right) {
                        if (nums[left] + nums[right] > newTarget) {
                            right --;
                        }
                        else if (nums[left] + nums[right] < newTarget) {
                            left ++;
                        }
                        else {
                            result.push_back({nums[i],nums[j],nums[left++],nums[right--]});
                            while(nums[left]  == nums[left-1]){
                                left++;
                            }
                            while(nums[right] == nums[right+1]) {
                                right ++;
                            }
                        }
                    }
                    while ( j < nums.size() && nums[j] == nums[j+1]) {
                        j++;
                    }
                }
                while(i<nums.size() && nums[i] == nums[i+1]) {
                    i++;
                }
            }
            return result;
        }
    

Log in to reply
 

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