[LeetCode] 18.四数之和

[Animenzzzz]

题目描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路：

C++解法：先自动排序（C++这些库函数，太爽了），常规循环。使用三层循环嵌套，一定要去重，要不然会超时。先定前两个位置的加数，后面两位从头和尾分别向中间偏移遍历。若四数之和等于target，则存下这一组；若小于target，左边开始移动；若大于target，右边开始移动

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>> res;
        sort(nums.begin(),nums.end());
        for (int i = 0; i < int(nums.size() - 3); i++)
        {
            for (int j = i+1; j < int(nums.size() - 2); j++)
            {
                //去重处理
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j+1;
                int right = nums.size() - 1;
                while (left<right)
                {
                    int sum = nums[i]+nums[j]+nums[right]+nums[left];
                    if(sum == target){
                        vector<int> tmp{nums[i],nums[j],nums[left],nums[right]};
                        res.insert(tmp);
                        left++;right--;
                    }else if(sum<target) left++;
                    else right--;
                }
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};