2sum
如果数组是无序的，先排序（n*logn），然后用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，则要想办法让sum 的值减小，所以此刻i 不动，j--，如果某一刻a[i]+a[j]<sum，则要想办法让sum 的值增大，所以此刻i++，j 不动。所以，数组无序的时候，时间复杂度最终为O（n*logn+n）=O（n*logn），若原数组是有序的，则不需要事先的排序，直接O（n）搞定，且空间复杂度还是O（1），此思路是相对于上述所有思路的一种改进。
Pair findSum(int *s,int n,int x)
{
//sort(s,s+n); 如果数组非有序的，那就事先排好序O（N*logN）
int *begin=s;
int *end=s+n-;
while(begin<end) //俩头夹逼，或称两个指针两端扫描法，很经典的方法，O（N）
{
if(*begin+*end>x)
{
--end;
}
else if(*begin+*end<x)
{
++begin;
}
else
{
return Pair(*begin,*end);
} }
return Pair(-,-);
}
3sum
vector<vector<int> > threeSum(vector<int> &num) {
if(num.empty())
return vector<vector<int> >();
sort(num.begin(),num.end());
vector<vector<int> > ret;
vector<int> tmp;
int n=num.size();
for(int i=;i<n-;i++)
{
if(i>&&num[i]==num[i-]) continue;//防止存在重复的元素
int target=-num[i];
int j=i+;
int k=n-;
while(j<k)
{
if(j<k&&k<n-&&num[k]==num[k+])
{
k--;
continue;
}
if(num[j]+num[k]==target)
{
tmp={num[i],num[j],num[k]};
ret.push_back(tmp);
j++;
k--;
}
else if(num[j]+num[k]<target)
{
j++;
}
else if(num[j]+num[k]>target)
k--;
}
}
return ret;
}4sum
vector<vector<int> > fourSum(vector<int> &num,int target)
{
if(num.empty())
return vector<vector<int> >();
sort(num.begin(),num.end());
vector<vector<int> > ret;
int n=num.size();
int i,j;
for(i=; i<n-; i++)
{
//只保留第一个不重复的，其余的都删了,因为left会选择重复的
if(i>=&&num[i]==num[i-])
continue;
for(j=n-; j>i+; j--)
{
//只保留最后一个不重复的，其余的都删了,因为right会选择重复的
if(j<n-&&num[j+]==num[j])
continue;
int left=i+;
int right=j-;
vector<int> tmp;
while(left<right)
{
//只保留最后一个不重复的，其余的都删了,因为left会选择重复的
if(right<j-&&num[right]==num[right+])
{
right--;
continue;
}
if(num[i]+num[j]+num[left]+num[right]==target)
{
tmp= {num[i],num[left],num[right],num[j]};
ret.push_back(tmp);
left++;
right--;
}
else if(num[i]+num[j]+num[left]+num[right]<target)
left++;
else if(num[i]+num[j]+num[left]+num[right]>target)
right--;
}
}
}
return ret;
}
任意连续数的和为sum（假设至少存在两个数）
void sum(int sum,int n)
{
if(sum<||n<)
return -;
int cursum=;
cursum=+;
int i=,j=;
while(j<=n)
{
if(cursum==sum)
{
int k=i;
while(k<=j)
{
cout<<k<<' ';
k++;
}
cout<<endl;
cursum-=i;
i++;
}
else if(cursum<sum)
{
j++;
cursum+=j;
}
else if(cursum>sum)
{
cursum-=i;
i++;
}
}
}
任意数的和为sum
用回溯的方法实现：
#include<iostream>
#include<vector>
using namespace std; void findhelper(int m,int n,int start,vector<int> &path)
{
if(m<)
return;
if(m==)
{
for(auto a:path)
cout<<a<<' ';
cout<<endl;
return;
}
for(int i=start; i<=n; ++i)
{
path.push_back(i);
findhelper(m-i,n,i+,path);
path.pop_back();
}
}
void findSum(int m,int n)
{
vector<int> path;
findhelper(m,n,,path);
} int main()
{
findSum(,);
}
用0-1背包法实现：
注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相关的问题。
- 如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum - n, n - 1)；
- 如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。
实现代码：
#include<iostream>
#include<vector>
using namespace std; void findhelper(int sum,int n,vector<int> &path)
{
//递归出口
if(sum<=||n<=)
return;
//输出找到的结果
if(sum==n)
{
for(int i=path.size()-; i>=; --i)
cout<<path[i]<<' ';
cout<<n<<endl;
}
path.push_back(n); //典型的01背包问题
findhelper(sum-n,n-,path);//放第n个元素
path.pop_back();
findhelper(sum,n-,path); //不放第n个元素
}
void findSum(int m,int n)
{
vector<int> path;
findhelper(m,n,path);
} int main()
{
findSum(,);
}
存在重复元素时，求和为sum
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std; void helper(vector<int> &num,vector<int> &path,int start,int sum)
{
if(sum==)
{
for(int i=;i<path.size();++i)
cout<<path[i]<<' ';
cout<<endl;
return;
}
if(sum<)
return;
for(int i=start;i<num.size();++i)
{
if(i>start&&num[i]==num[i-])
continue;
path.push_back(num[i]);
helper(num,path,i+,sum-num[i]);
path.pop_back();
}
}
void findSum(vector<int> &num,int sum)
{
vector<int> path;
sort(num.begin(),num.end());
helper(num,path,,sum);
} int main()
{
vector<int> num={,,,,,};
findSum(num,);
}