Straight-forward extension from 3sum


  • 0
    T

    A modified version from 3sum, check out the original 3sum post here, Credit goes to Stefan :)
    https://leetcode.com/discuss/38418/20-lines-68ms-c-solution-used-two-pointers-similar-to-2sum

    Basically another while loop wrapped around the 3sum soluation.

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> sol;
            sort(nums.begin(), nums.end());
            int i = 0, last = nums.size()-1;
            while (i < last){
                int j = i+1, a = nums[i];
                while (j < last){
                    int k = j+1, m = last, b = nums[j];;
                    while (k < m){
                        int c = nums[k], d = nums[m];
                        int sum = a + b + c + d;
                        if (sum == target) sol.push_back({a,b,c,d});
                        if (sum <= target) while(c == nums[k] && k < m) k++;
                        if (sum >= target) while(d == nums[m] && k < m) m--;
                    }
                    while (b == nums[j] && j < last) j++;
                }
                while (a == nums[i] && i < last) i++;
            }
            return sol;
        }

Log in to reply
 

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