题解 | #牛群的标签和#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目：找出所有和为0且不重复的四元组。

题目考察的知识点：

• 数组排序
• 双指针技巧

题目解答方法的文字分析：

这个问题可以使用双指针技巧来解决。首先，我们对数组进行排序，然后使用四个指针 i, j, left, right 来表示四元组的元素。其中 i 和 j 是遍历数组的两个指针，left 和 right 是双指针来寻找剩下两个元素。

我们固定 i 和 j，然后通过移动 left 和 right 指针来寻找剩下两个元素，使得四个元素的和为目标值 target。为了避免重复，我们需要在找到一个四元组后，分别跳过相同的元素。

举个例子来说明：

假设我们有一个排序后的数组 nums = [-2, -1, 0, 0, 1, 2]，目标值 target = 0。我们初始化指针 i 和 j 分别指向第一个元素和第二个元素 -2 和 -1。然后，我们使用双指针 left 和 right 来寻找剩下两个元素，使得 -2、-1、left 和 right 的和为 0。在这个过程中，我们要注意跳过相同的元素。例如，如果 left 和 right 分别指向了 0 和 1，此时和为 -2，小于目标值，我们需要移动 left 指针，跳过重复的元素 0，直到 left 指向了第二个 2，此时和为 0，满足条件，我们记录这个四元组。然后继续寻找下一个四元组，直到遍历完所有可能的组合。

本题解析所用的编程语言：C++

完整且正确的编程代码（注释清晰完整）：

class Solution {
public:
    vector<vector<int> > fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> result;

        if (n < 4)
            return result;

        // Step 1: Sort the array
        sort(nums.begin(), nums.end());

        // Step 2: Use two pointers to find the remaining two elements
        for (int i = 0; i < n - 3; ++i) {
            // Skip duplicates
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            for (int j = i + 1; j < n - 2; ++j) {
                // Skip duplicates
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;

                int left = j + 1;
                int right = n - 1;

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum == target) {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});

                        // Skip duplicates
                        while (left < right && nums[left] == nums[left + 1])
                            ++left;

                        while (left < right && nums[right] == nums[right - 1])
                            --right;

                        ++left;
                        --right;
                    } else if (sum < target) {
                        ++left;
                    } else {
                        --right;
                    }
                }
            }
        }

        return result;
    }
};