2sum

如果數(shù)組是無序的，先排序（n*logn），然后用兩個(gè)指針i，j，各自指向數(shù)組的首尾兩端，令i=0，j=n-1，然后i++，j--，逐次判斷a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，則要想辦法讓sum 的值減小，所以此刻i 不動(dòng)，j--，如果某一刻a[i]+a[j]<sum，則要想辦法讓sum 的值增大，所以此刻i++，j 不動(dòng)。所以，數(shù)組無序的時(shí)候，時(shí)間復(fù)雜度最終為O（n*logn+n）=O（n*logn），若原數(shù)組是有序的，則不需要事先的排序，直接O（n）搞定，且空間復(fù)雜度還是O（1），此思路是相對(duì)于上述所有思路的一種改進(jìn)。

?

Pair findSum(int *s,int n,int x) { //sort(s,s+n); 如果數(shù)組非有序的，那就事先排好序O（N*logN）int *begin=s;int *end=s+n-1;while(begin<end) //倆頭夾逼，或稱兩個(gè)指針兩端掃描法，很經(jīng)典的方法，O（N） {if(*begin+*end>x){--end;}else if(*begin+*end<x){++begin;}else{return Pair(*begin,*end);}178}return Pair(-1,-1); }

?

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=0;i<n-2;i++){if(i>0&&num[i]==num[i-1]) continue;//防止存在重復(fù)的元素int target=-num[i];int j=i+1;int k=n-1;while(j<k){if(j<k&&k<n-1&&num[k]==num[k+1]){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=0; i<n-3; i++){//只保留第一個(gè)不重復(fù)的，其余的都刪了,因?yàn)閘eft會(huì)選擇重復(fù)的if(i>=1&&num[i]==num[i-1])continue;for(j=n-1; j>i+2; j--){//只保留最后一個(gè)不重復(fù)的，其余的都刪了,因?yàn)閞ight會(huì)選擇重復(fù)的if(j<n-1&&num[j+1]==num[j])continue;int left=i+1;int right=j-1;vector<int> tmp;while(left<right){//只保留最后一個(gè)不重復(fù)的，其余的都刪了,因?yàn)閘eft會(huì)選擇重復(fù)的if(right<j-1&&num[right]==num[right+1]){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;}

任意連續(xù)數(shù)的和為sum（假設(shè)至少存在兩個(gè)數(shù)）

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<<' ';k++;}cout<<endl;cursum-=i;i++;}else if(cursum<sum){j++;cursum+=j;}else if(cursum>sum){cursum-=i;i++;}} }

任意數(shù)的和為sum

用回溯的方法實(shí)現(xiàn)：

#include<iostream> #include<vector> using namespace std;void findhelper(int m,int n,int start,vector<int> &path) {if(m<0)return;if(m==0){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+1,path);path.pop_back();} } void findSum(int m,int n) {vector<int> path;findhelper(m,n,1,path); }int main() {findSum(15,20); }

?用0-1背包法實(shí)現(xiàn)：

注意到取n，和不取n個(gè)區(qū)別即可，考慮是否取第n個(gè)數(shù)的策略，可以轉(zhuǎn)化為一個(gè)只和前n-1個(gè)數(shù)相關(guān)的問題。

• 如果取第n個(gè)數(shù)，那么問題就轉(zhuǎn)化為“取前n-1個(gè)數(shù)使得它們的和為sum-n”，對(duì)應(yīng)的代碼語句就是sumOfkNumber(sum - n, n - 1)；
• 如果不取第n個(gè)數(shù)，那么問題就轉(zhuǎn)化為“取前n-1個(gè)數(shù)使得他們的和為sum”，對(duì)應(yīng)的代碼語句為sumOfkNumber(sum, n - 1)。

實(shí)現(xiàn)代碼：

#include<iostream> #include<vector> using namespace std;void findhelper(int sum,int n,vector<int> &path) {
　　//遞歸出口if(sum<=0||n<=0)return;
　　//輸出找到的結(jié)果if(sum==n){for(int i=path.size()-1; i>=0; --i)cout<<path[i]<<' ';cout<<n<<endl;}path.push_back(n); //典型的01背包問題findhelper(sum-n,n-1,path);//放第n個(gè)元素path.pop_back();findhelper(sum,n-1,path); //不放第n個(gè)元素 } void findSum(int m,int n) {vector<int> path;findhelper(m,n,path); }int main() {findSum(15,20); }

?存在重復(fù)元素時(shí)，求和為sum

#include<iostream> #include<vector> #include<algorithm> using namespace std;void helper(vector<int> &num,vector<int> &path,int start,int sum) {if(sum==0){for(int i=0;i<path.size();++i)cout<<path[i]<<' ';cout<<endl;return;}if(sum<0)return;for(int i=start;i<num.size();++i){if(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<int> &num,int sum) {vector<int> path;sort(num.begin(),num.end());helper(num,path,0,sum); }int main() {vector<int> num={1,2,1,3,0,1};findSum(num,3); }

?

總結(jié)

以上是生活随笔為你收集整理的2sum、3sum、4sum以及任意连续的数的和为sum、任意连续或者不连续的数的和为sum...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。