leetcode：18. 四数之和

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例：

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

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

解答 & 代码

双指针（相向）
递归求 n 数之和（nSum），每次递归求 n - 1 数之和，递归结束条件为 n = 2，求两数之和

class Solution {
private:
    // 递归求解 n 数之和问题
    // 返回升序数组 nums[start, end] 的 n 数之和 == target 的所有 n 元组
    vector<vector<int>> nSum(vector<int>& nums, int start, int end, int n, long long target)
    {
        vector<vector<int>> result;
        // 递归结束条件：当 n == 2 时，直接求两数之和
        if(n == 2)
        {
            int left = start;
            int right = end;
            while(left < right)
            {
                if(left != start && nums[left] == nums[left - 1])    // 去重
                {
                    ++left;
                    continue;
                }
                // 双指针
                if(nums[left] + nums[right] == target)
                {
                    result.push_back(vector<int>{nums[left], nums[right]});
                    ++left;
                    --right;
                }
                else if(nums[left] + nums[right] < target)
                    ++left;
                else
                    --right;
            }
        }
        // 否则，遍历数组，依次以元素 nums[i] 作为第一个数，递归求 n-1 Sum
        else
        {
            for(int i = start; i <= end; ++i)
            {
                if(i != start && nums[i] == nums[i - 1])    // 去重
                    continue;

                vector<vector<int>> n1sumResult = nSum(nums, i + 1, end, n - 1, target - nums[i]);
                for(int j = 0; j < n1sumResult.size(); ++j)
                {
                    n1sumResult[j].push_back(nums[i]);
                    result.push_back(n1sumResult[j]);
                }
            }
        }
        return result;
    }
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());        // 先排序
        return nSum(nums, 0, nums.size() - 1, 4, target);
    }
};

复杂度分析：设数组长为 n

时间复杂度：需要两重循环来枚举前两个数，时间复杂度；再通过双指针枚举剩下的两个数，时间复杂度 O(n)
空间复杂度 O(log n)：排序的空间复杂度

执行结果：

执行结果：通过

执行用时：84 ms, 在所有 C++ 提交中击败了 58.50% 的用户
内存消耗：13.2 MB, 在所有 C++ 提交中击败了 7.00% 的用户

hot 100

[中等] 18. 四数之和

题目

解答 & 代码