2sum、3sum、4sum以及任意连续的数的和为sum、任意连续或者不连续的数的和为sum...
阅读量：6249 次
发布时间：2019-06-22
本文共 3521 字，大约阅读时间需要 11 分钟。
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-1; while(begin x) { --end; } else if(*begin+*end
3sum
vector > threeSum(vector &num) { if(num.empty()) return vector >(); sort(num.begin(),num.end()); vector > ret; vector tmp; int n=num.size(); for(int i=0;i 0&&num[i]==num[i-1]) continue;//防止存在重复的元素 int target=-num[i]; int j=i+1; int k=n-1; while(j target) k--; } } return ret; }
4sum
vector > fourSum(vector &num,int target) { if(num.empty()) return vector >(); sort(num.begin(),num.end()); vector > ret; int n=num.size(); int i,j; for(i=0; i =1&&num[i]==num[i-1]) continue; for(j=n-1; j>i+2; j--) { //只保留最后一个不重复的，其余的都删了,因为right会选择重复的 if(j
tmp; while(left
target) right--; } } } return ret; } 任意连续数的和为sum（假设至少存在两个数）
void sum(int sum,int n){ if(sum<0||n<2) return -1; int cursum=0; cursum=1+2; int i=0,j=1; while(j<=n) { if(cursum==sum) { int k=i; while(k<=j) { cout< <<' '; k++; } cout< sum) { cursum-=i; i++; } }} 任意数的和为sum
用回溯的方法实现：
#include #include using namespace std;void findhelper(int m,int n,int start,vector &path){ if(m<0) return; if(m==0) { for(auto a:path) cout< <<' '; cout<
path; findhelper(m,n,1,path);}int main(){ findSum(15,20);}
用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 #include using namespace std;void findhelper(int sum,int n,vector &path){ //递归出口 if(sum<=0||n<=0) return; //输出找到的结果 if(sum==n) { for(int i=path.size()-1; i>=0; --i) cout< <<' '; cout< <
path; findhelper(m,n,path);}int main(){ findSum(15,20);}
#include #include #include using namespace std;void helper(vector &num,vector &path,int start,int sum){ if(sum==0) { for(int i=0;i start&&num[i]==num[i-1]) continue; path.push_back(num[i]); helper(num,path,i+1,sum-num[i]); path.pop_back(); }}void findSum(vector &num,int sum){ vector path; sort(num.begin(),num.end()); helper(num,path,0,sum);}int main(){ vector num={ 1,2,1,3,0,1}; findSum(num,3);}