编程之美之高速寻找多个数满足给定条件

一、寻找三个数之和等于给定值

分析：方法类似与2Sum。就是先对数组进行排序，时间复杂度为O(nlogn)，然后固定一个数，用两个指针进行遍历，找到三个数之和等于给定的值就可以，时间复杂度为O(n^2)。详细可提交于leetcode：https://oj.leetcode.com/problems/3sum/，代码例如以下：

vector<vector<int> > threeSum(vector<int> &num,int target){
	vector<vector<int> >res;
	int i,j,k,size = num.size();
	sort(num.begin(),num.end());
	for(i=0;i<size;i++)//固定一个数
	{
		if(i>0 && num[i] == num[i-1])continue;//防止反复计算，比如1 1 -1 0，target=0，假设没有该推断，结果会有两个 1 -1 0
		j = i + 1;//循环遍历另外两个指针
		k = size-1;
		while(j < k)
		{
			if(num[i]+num[j]+num[k] == target)
			{
				vector<int> tmp;
				tmp.push_back(num[i]);
				tmp.push_back(num[j]);
				tmp.push_back(num[k]);
				res.push_back(tmp);
				j++;
				k--;
				while(num[j] == num[j-1])j++;
				while(num[k] == num[k+1])k++;
			}
			if(num[i]+num[j]+num[k] > target)k--;
			else j++;
		}
	}
	return res;
}

分析：要找出的三个数可能不是恰好等于目标值。方法类似于上面的分析，仅仅是在每次三个数之和推断时。当三个数之和小于等于或大于等于给定target时，不光要移动指针，还要还当前最接近的和比較。留下最接近的和。题目见leetcode：3Sum Closet,代码例如以下：

bool flag = true;//用于第一次记录最接近的三个数之和
int threeSumClosest(vector<int> &num, int target)
{
	sort(num.begin(),num.end());
	int i,j,k,currentSum=0,size = num.size();
	for(i=0;i<size;i++)
	{
		if(j>0 && num[j] == num[j-1])continue;
		j = i+1;
		k = size -1;
		while(j < k)
		{
			if(abs(num[i]+num[j]+num[k]-target)<abs(currentSum-target) || flag)
			{
				currentSum = num[i]+num[j]+num[k];//替换最接近的三个数
			}
			flag = false;
			if(abs(num[i]+num[j]+num[k]) < target)
			{
				j++;
				while(num[j] == num[j-1])j++;
			}
			else
			{
				k--;
				while(num[k] == num[k+1])k--;
			}
		}
	}
	return currentSum;
}

方法和三个数的和一样，仅仅是多了一层循环，据说有更快的方法。能力有限，没写出来，希望高手指点。见leetcode上4Sum，代码例如以下：

vector<vector<int> > fourSum(vector<int> &num, int target)
{
	sort(num.begin(),num.end());
	vector<vector<int> > res;
	int i,j,k,t,size = num.size();
	for(i=0;i<size-3;i++)
	{
		if(i>0 && num[i]==num[i-1])continue;
		for(j=i+1;j<size-2;j++)
		{
			if(j> i+1 && num[j] == num[j-1])continue;
			k = j+1;
			t = size-1;
			while(k < t)
			{
				if(num[i] + num[j] + num[k] + num[t] == target)
				{
					vector<int> tmp;
					tmp.push_back(num[i]);
					tmp.push_back(num[j]);
					tmp.push_back(num[k]);
					tmp.push_back(num[t]);
					res.push_back(tmp);
					k++;
					t--;
					while(k < t && num[k] == num[k-1])k++;
					while(k < t && num[t] == num[t+1])t--;
				}
				else if(num[i] + num[j] + num[k] + num[t] > target) t--;
				else k++;
			}
		}
	}
	return res;
}

分析：因为能够是随意个数，所以使用递归比較方便，简单的说就是顺序遍历每个数。类似于背包问题。取的话结果有哪些，不取的话结果有哪些，从而得出全部的结果，不知道还有没有高效的算法，代码例如以下：

void anySum(vector<int> numbers,int target,int index,vector<int>& currSum,vector<vector<int> >& res)
{
	if(index > numbers.size())return;
	if(target == 0)
	{
		res.push_back(currSum);//获得一个结果
		return;
	}
	currSum.push_back( numbers[index]);//本次取该数进行递归
	target -= numbers[index];
	anySum(numbers,target,index+1,currSum,res);
	currSum.pop_back();//本次不取该数进行递归
	target += numbers[index];
	anySum(numbers,target,index+1,currSum,res);
}
vector<vector<int> > anySum(vector<int> numbers,int target)
{
	vector<vector<int> > res;
	vector<int> currSum;
	anySum(numbers,target,0,currSum,res);
	return res;
}