题解 | #牛群的标签和# 枚举 + 双指针

知识点

双指针

思路

我们将数组排序之后，枚举前两个元素，剩下的两个元素用双指针来得到，这样的时间复杂度是

如果当前元素和上一次的元素是相等的，我们就可以跳过达到去重的目的。

AC Code (C++)

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        vector<int> path;
        for (int i = 0; i < n; i ++) {
            if (i > 0 and nums[i] == nums[i - 1]) continue;
            path.emplace_back(nums[i]);
            for (int j = i + 1; j < n; j ++) {
                if (j > i + 1 and nums[j] == nums[j - 1]) continue;
                path.emplace_back(nums[j]);
                // [j + 1, n - 1] 双指针
                int k = target - nums[i] - nums[j];
                for (int a = j + 1, b = n - 1; a < b; a ++) {
                    if (a > j + 1 and nums[a] == nums[a - 1]) continue;
                    path.emplace_back(nums[a]);
                    while (a < b and (nums[a] + nums[b] > k or (b + 1 < n and nums[b] == nums[b + 1]))) b --;
                    if (a < b and nums[a] + nums[b] == k) {
                        path.emplace_back(nums[b]);
                        res.push_back(path);
                        path.pop_back();
                    }
                    path.pop_back();
                }
                path.pop_back();
            }
            path.pop_back();
        }
        return res;
    }
};