leetcode 18. 4Sum

浅浅的花香味﹌ 2022-07-29 08:40 143阅读 0赞

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)

class Solution {
    	struct Info
    	{
    		vector<pair<int, int>>pre;//pair<int,int>里的first代表sinnums里的index,second代表个数  
    		int remainsize;//剩余的数字个数  
    		int remainvalue;//剩余的值  
    	};
    	vector<vector<int>>re;
    	void choose_one(int&k, vector<Info>&candi, map<int, int>&count, vector<int>sinnums)
    	{
    		vector<Info>newcandi;
    		if (k == 1)
    		{
    			for (int i = 0; i < candi.size(); i++)//考虑0  
    				if (candi[i].remainvalue%candi[i].remainsize == 0)
    				{
    					int nxtnum = candi[i].remainvalue / candi[i].remainsize;
    					if (nxtnum>sinnums[candi[i].pre.back().first] && count.find(nxtnum) != count.end()
    						&& count[nxtnum] >= candi[i].remainsize)
    					{
    						vector<int>aa;
    						for (int j = 0; j < candi[i].pre.size(); j++)
    							for (int h = 0; h < candi[i].pre[j].second; h++)
    								aa.push_back(sinnums[candi[i].pre[j].first]);
    						for (int j = 0; j < candi[i].remainsize; j++)
    							aa.push_back(nxtnum);
    						re.push_back(aa);
    					}
    				}
    			k--;
    			return;
    		}
    		else
    		{
    			for (int i = 0; i < candi.size(); i++)
    			{
    				for (int j = 1; j <= (candi[i].remainsize - k + 1); j++)
    				{
    					for (int h = candi[i].pre.back().first + 1; (h < sinnums.size() - k + 1); h++)
    					{
    						//粗略做判断，减小候选集大小  
    						if (candi[i].remainvalue <= sinnums[h] * j + sinnums.back()* (candi[i].remainsize - j) 
    							&& candi[i].remainvalue >= sinnums[h] * j + sinnums[h + 1] * (candi[i].remainsize - j) 
    							&& j <= count[sinnums[h]])
    						{
    							Info info;
    							info.pre = candi[i].pre;
    							info.pre.push_back(pair<int, int>(h, j));
    							info.remainsize = candi[i].remainsize - j;
    							info.remainvalue = candi[i].remainvalue - j*sinnums[h];
    							newcandi.push_back(info);
    						}
    					}
    				}
    			}
    			k--;
    			candi = newcandi;
    			return;
    		}
    	}
    
    public:
    	vector<vector<int>> fourSum(vector<int>& nums, int target)
    	{
    		if (nums.empty())
    			return re;
    		map<int, int>count;
    		for (int i = 0; i < nums.size(); i++)
    			count[nums[i]]++;
    		map<int, int>::iterator it = count.end(); it--;
    		if (target >= 0 && count.begin()->first> target
    			|| target < 0 && it->first < target)
    			return re;
    		vector<int>sinnums;
    		for (it = count.begin(); it != count.end(); it++)
    			sinnums.push_back(it->first);
    		int neednum = 4;
    		//答案里只有一种数字  
    		if (target%neednum==0&&count.find(target / neednum) != count.end() && count[target / neednum] >= neednum)
    		{
    			vector<int>aa(neednum, target / neednum);
    			re.push_back(aa);
    		}
    		for (int i = 0; i < sinnums.size(); i++)
    		{
    			//答案里有k种数字,2<=k<=neednum  
    			for (int k = 2; k <= neednum; k++)
    			{
    				if (sinnums.size() - i >= k)
    				{
    					int jjmax = neednum - k + 1 < count[sinnums[i]] ? neednum - k + 1 : count[sinnums[i]];
    					for (int j = 1; j <= jjmax; j++)
    					{
    						Info inf;
    						inf.pre.push_back(pair<int, int>(i, j));
    						inf.remainsize = neednum - j;
    						inf.remainvalue = target - j*sinnums[i];
    						vector<Info>candi;
    						candi.push_back(inf);
    						int kk = k - 1;
    						while (kk > 0)
    							choose_one(kk, candi, count, sinnums);
    					}
    				}
    			}
    		}
    		return re;
    	}
    };

accepted

其实哥的这个代码实用性很强，神马4sum，5sum。。。照单全收，neednum一改，一撸到底，卧槽，有没有。

然后往下一看，额，来了个3sum，好吧，copy、paste、accepted，尼玛，这才是复用啊，根本不用改的。

（请忽略以上chui扯niu淡bi）