4个数之和

给你一个由 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
你可以按 任意顺序 返回答案 。

样例1：

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

样例2：

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

提示：

$1<=nums.length<=200$
$-10^9<=nums[i]<=10^9$
$-10^9<=target<=10^9$

题解

双指针

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> fourSum(vector<int> &nums, int target)
{
   
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int k = 0; k < nums.size(); k++)
    {
   
        // 去重
        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;
            int right = nums.size() - 1;
            while (right > left)
            {
   
                //if (nums[k] + nums[i] + nums[left] + nums[right] > target)
                if (nums[k] + nums[i] > target - (nums[left] + nums[right]))
                    right--;
                else if (nums[k] + nums[i] < target - (nums[left] + nums[right]))
                    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++;
                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
    }
    return result;
}

int main()
{
   
    vector<int> numbers = {
   1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSum(numbers, target);
    for (int i = 0; i < result.size(); i++)
    {
   
        for (int j = 0; j < result[i].size(); j++)
        {
   
            if (j == 0)
                cout << "(";
            printf("%2d ", result[i][j]);
            if (j != result[i].size() - 1)
                cout << ",";
            else
                cout << ")";
        }

        printf("\n");
    }
    return 0;
}

DFS+剪枝

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> ans;
vector<int> myNums, subans;
int tar, numSize;
void DFS(int low, int sum)
{
   
    if (sum == tar && subans.size() == 4)
    {
   
        ans.emplace_back(subans);
        return;
    }
    for (int i = low; i < numSize; ++i)
    {
   
        if (numSize - i < long(4 - subans.size()))
        {
    //剪枝
            return;
        }
        if (i > low && myNums[i] == myNums[i - 1])
        {
    //去重
            continue;
        }
        if (i < numSize - 1 && sum + myNums[i] + long(3 - subans.size()) * myNums[i + 1] > tar)
        {
    //剪枝
            return;
        }
        if (i < numSize - 1 && sum + myNums[i] + long(3 - subans.size()) * myNums[numSize - 1] < tar)
        {
    //剪枝
            continue;
        }
        subans.emplace_back(myNums[i]);
        DFS(i + 1, myNums[i] + sum);
        subans.pop_back();
    }
    return;
}

vector<vector<int>> fourSum(vector<int> &nums, int target)
{
   
    sort(nums.begin(), nums.end());
    myNums = nums;
    tar = target;
    numSize = nums.size();
    if (numSize < 4)
    {
   
        return ans;
    }
    DFS(0, 0);
    return ans;
}

int main()
{
   
    vector<int> numbers = {
   1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSum(numbers, target);
    for (int i = 0; i < result.size(); i++)
    {
   
        for (int j = 0; j < result[i].size(); j++)
        {
   
            if (j == 0)
                cout << "(";
            printf("%2d ", result[i][j]);
            if (j != result[i].size() - 1)
                cout << ",";
            else
                cout << ")";
        }

        printf("\n");
    }
    return 0;
}