LeetCode 4Sum - c++编程基础

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target Find all unique quadruplets in the array which gives the sum of target.

Note:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:

(-1, 0, 0, 1)

(-2, -1, 1, 2)

(-2, 0, 0, 2)

这道题和3Sum的思路是一样的。时间复杂度是O(n^3)，增加了一个外循环判断，程序长了点，总的程序结构也是一样的。

#include  
#include  
#include  
#include  
  
using namespace std;  
  
class Solution {  
public:  
    vector > fourSum(vector &num, int target)   
    {  
        vector > result;  
        if (num.size() < 4)  
        {  
            return result;  
        }  
        vector fNum(4);  
        sort(num.begin(), num.end());  
  
        int i = 0, j = 0, k = 0, r = num.size()-1;  
        while (i < r-2)  
        {  
            for (j = i+1; j < r-1;)  
            {  
                //Notice: don't forget to reset the value of r = num.size()-1;  
                for (k = j+1, r = num.size()-1; k < r; )  
                {  
                    int temp = num[i] + num[j] + num[k] + num[r];  
                    if (temp == target)  
                    {  
                        fNum[0] = num[i]; fNum[1] = num[j]; fNum[2] = num[k]; fNum[3] = num[r];  
                        result.push_back(fNum);  
                        k++; r--;  
                        //注意判断重复的时候需要放进判断条件括号里面，因为没有移动的时候不需要判断  
                        //k和r都不一定每次移动的  
                        while (k




 vi(a, a+len);  
    cout<<"The array is:\n";  
    for (auto x:vi)  
        cout< > vt = solu.fourSum(vi, 10);  
  
    for (auto x:vi)  
        cout<