（每日一练C++）CC132 4数之和

ゝ一纸荒年。 2023-10-04 17:54 36阅读 0赞

### 描述 ###

给出一个有n个元素的数组S，S中是否有元素a,b,c和d满足a+b+c+d=目标值？找出数组S中所有满足条件的四元组。

注意：

1.  四元组（a、b、c、d）中的元素必须按非降序排列。（即a≤b≤c≤d）
2.  解集中不能包含重复的四元组。

例如：给出的数组 S = {10 0 -10 0 -20 20}, 目标值 = 0.
        给出的解集应该是：
        (-10,  0, 0, 10)
        (-20, -10, 10, 20)
        (-20,  0, 0, 20)

class Solution {
        vector<int> d;
        vector<vector<int> > z;
        set<vector<int> > da;
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            int i,j,k,q,t;
            sort(num.begin(),num.end());
            for(k=0;k<num.size();k++)
                for(q=k+1;q<num.size();q++)
               	{
                	t=target-num[k]-num[q];
                	for(i=0,j=num.size()-1;i<j;)
                        if(i==q||i==k) i++;
                        else if(j==q||j==k) j--;
                        else
                        {
                        	if(num[i]+num[j]==t)
                            {
                                d.push_back(num[k]);d.push_back(num[q]);
                                d.push_back(num[i]);d.push_back(num[j]);
                                sort(d.begin(),d.end());
                                da.insert(d);
                                d.clear();
                                i++;j--;
                            }
                        	else if(num[i]+num[j]<t) i++;
                            else j--;
                    	}
            	}
            set<vector<int> >::iterator it;
            for(it=da.begin();it!=da.end();z.push_back(*it),it++);
            return z;
        }
    };