18.4Sum

Taags: Array Medium

Links: https://leetcode.com/problems/4sum/

---

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]
]

---

Answer:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        if (nums.size() < 4) return result;

        for (int i = 0; i < nums.size() - 3; ++i){
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int lowLevel = target - nums[i];

            for (int j = i + 1; j < nums.size() - 2; ++j){

                if ((j - i) > 1 && nums[j] == nums[j - 1]) continue;
                int k = j + 1, m = nums.size() - 1;

                while (k < m){
                    int tmp = nums[j] + nums[k] + nums[m];
                    if (tmp < lowLevel) 
                        ++k;
                    else if (tmp > lowLevel)
                        --m;
                    else{
                        result.push_back({nums[i], nums[j], nums[k], nums[m]});
                        while(k < m && nums[k] == nums[k + 1]) ++k;
                        while(k < m && nums[m] == nums[m - 1]) --m;
                        ++k;
                        --m;
                    }
                }
            }

        }

        return result;
    }
};