LeetCode_18_四数之和

题目描述：

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

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

示例：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [], target = 0
输出：[]

提示：
1. 0 <= nums.length <= 200
2. -10^9 <= nums[i] <= 10^9
3. -10^9 <= target <= 10^9

解法1：双指针

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 k = 0; k < nums.size(); k++) {

            //错误写法：这道题目target可能为负数
            //if (nums[k] > target) return result;

            //去重
            if (k > 0 && nums[k] == nums[k - 1]) continue;

            for (int i = k + 1; i < nums.size(); i++) {

                //去重
                if (i > k + 1 && nums[i] == nums[i - 1]) continue;

                int left = i + 1, right = nums.size() - 1;

                while (right > left) {

                    //⭐️注意必须强转成long int，因为-10^9 <= nums[i] <= 10^9
                    //输入：[1000000000, 1000000000, 1000000000, 1000000000] 0
                    //输出：[]
                    //三数之和那道题不需要强转是因为它前面有判断条件：if (nums[i] > 0) return result;
                    if ((long int)nums[k] + (long int)nums[i] + (long int)nums[left] + (long int)nums[right] > target) right--;

                    else if ((long int)nums[k] + (long int)nums[i] + (long int)nums[left] + (long int)nums[right] < target) left++;
                    
                    else {

                        result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});

                        //去重应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        //找到答案时，双指针同时收缩
                        left++;
                        right--;
                    }
                }

            }
        }

        return result;
    }
};