LeetCode(C++)刷题计划：18-四数之和

18-四数之和

@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com

Category	Difficulty	Pass rate	Tags	Companies
algorithms	Medium	36.01%	array / hash-table / two-pointers	linkedin

1. 题目

给定一个包含 $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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

2. 解法

2.1 解法一：双指针法

与前面三数之和类似，还是采用双指针法，双指针是用来选择后两个数的，因此前面还需要两个循环，来选择前两个数。

需要注意的是这四个数，都需要进行去重处理。双指针的去重我不再赘述，详情参考 LeetCode(C++)刷题计划：15-三数之和。

下面我们讲一下，前两个数的去重代码，以 nums = [0, 0, 1, 1, 1, 2] 为例。

首先第一个数的去重代码 if (i > 0 && nums[i] == nums[i - 1]) continue;
1. nums[i] == nums[i - 1] 的作用就是判断当前数是否和前一个数相等。
2. i > 0，是为了防止第一个数的 nums[0] == nums[-1]，这样数组就越界了。
第二个数的去重代码 if (k > i + 1 && nums[k] == nums[k - 1]) continue;
1. nums[k] == nums[k - 1] 的作用和前面一样。
2. k > i + 1 的目的倒不是防止越界，因为不可能越界。它主要为了防止过度去重。
  举个例子：nums = [0, 0, 1, 1, 1, 2]。
  当 i = 2 时, nums[i] = 1。此时 k = i + 1 = 3, nums[k] = 1。
  如果我们没有 k > i + 1 这句，他会认为 nums[k] 是重复数据(因为 nums[k] == nums[k - 1])。但是实际上是nums[k] 和 nums[i] (k = i + 1)在比较是否相等，然而这两个数是可以相等的。
  我们需要避免的是，在同一个 nums[i] 下，连续的 nums[k] 不能相等， nums[i] 不在我们的比较范围内。

执行用时: 76 ms, 在所有 cpp 提交中击败了42.69%的用户
内存消耗: 8.9 MB, 在所有 cpp 提交中击败了96.88%的用户

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