LeetCode 18. 四数の和(C++)

タイトル:
n個の整数を含む配列numsとターゲット値targetを与え、numsにa+b+c+dの値がtargetと等しいように4つの要素a,b,c,dが存在するかどうかを判断する.条件を満たし、繰り返さないすべての四元グループを見つけます.
注意:
答えに重複する四元グループを含めてはいけません.
例:

     nums = [1, 0, -1, 0, -2, 2]，  target = 0。

           ：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

考え方:
この問題はLeetCode 15の3数の和と似ているが,外層は新しい目標値を求めるために2サイクルを必要とし,2数の和に変換する問題であり,結果の重複を防止するためにsetを用いて結果を保存する.具体的なコードは以下の通りである.配列をソートしたため、コードはさらに最適化することができる.例えば、最初のforサイクル内で4*num[i]が所定のtargetより大きいかどうかを判断し、それより大きいと、今回のサイクルでは結果が見つからないに違いない.continue、このように推定する.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>> res;
        if(nums.size() < 4)
            return vector<vector<int>>(res.begin(),res.end());
        sort(nums.begin(),nums.end());
        int l, r, sum;
        for(int i = 0; i 3; i++){
            for(int j = i + 1; j < nums.size() - 2; j++){
                l = j + 1;
                r = nums.size() - 1;
                sum = target - nums[i] - nums[j];
                while(l < r){
                    if(nums[l] + nums[r] == sum){
                        vector<int> scheme = {nums[i],nums[j],nums[l],nums[r]};
                        res.insert(scheme);
                        while(l < r && nums[l + 1] == nums [l]) ++l;
                        while(l < r && nums[r - 1] == nums [r]) --r;
                        ++l;
                        --r;
                    }
                    else if(nums[l] + nums[r] < sum)
                        ++l;
                    else 
                        --r;
                }
            }
        }
        return vector<vector<int>>(res.begin(),res.end());

    }
};