18. 4Sum

• Difficulty: Medium

• Topics: Array, Hash Table, Two Pointers

• Similar Questions:

  • Two Sum

  • 3Sum

  • 4Sum II

Problem:

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solutions:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4)    return {};
        sort(nums.begin(), nums.end());

        vector<vector<int>> ret;
        for (int a = 0; a < nums.size() - 3; ++a) {
            if (a > 0 && nums[a] == nums[a - 1])    continue;
            for (int b = a + 1; b < nums.size() - 2; ++b) {
                if (b > a + 1 && nums[b] == nums[b-1])  continue;
                int c = b + 1;
                int d = nums.size() - 1;
                while (c < d) {
                    int val = nums[a] + nums[b] + nums[c] + nums[d];
                    if (val == target) {
                        ret.push_back({nums[a], nums[b], nums[c], nums[d]});
                        do {
                        ++c;
                        --d;
                        } while (c < d && nums[c] == nums[c-1] && nums[d] == nums[d+1]);
                    } else if (val < target) {
                        ++c;
                    } else {
                        --d;
                    }
                }
            }
        }

        return ret;

    }
};