小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫(xiě)出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))。沒(méi)多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22?，F(xiàn)在把問(wèn)題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck! 輸出描述:
輸出所有和為S的連續(xù)正數(shù)序列。序列內(nèi)按照從小至大的順序，序列間按照開(kāi)始數(shù)字從小到大的順序
/*
用兩個(gè)數(shù)字begin和end分別表示序列的最大值和最小值，
首先將begin初始化為1，end初始化為2.
如果從begin到end的和大于s，我們就從序列中去掉較小的值(即增大begin),
相反，只需要增大end。
終止條件為：一直增加begin到(1+sum)/2并且end小于sum為止
*/
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum)
{
vector<vector<int> > res;
if(sum < 3) return res;
int mid = (sum + 1)>>1;
int begin = 1;
int end = 2;
int cur = begin + end;
while(begin < mid && end < sum)
{
while(cur > sum)
{
cur -= begin;
begin++;
}
if(cur == sum)
InsertRes(begin,end,res);
end++;
cur += end;
}
return res;
}
void InsertRes(int begin,int end,vector<vector<int> > &res)
{
vector<int> temp;
for(int i = begin;i<=end;i++)
temp.push_back(i);
res.push_back(temp);
}
};
另一種方法：
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> allres;
int phigh=2;
int plow=1;
while(phigh>plow){
int cur=(phigh+plow)*(phigh-plow+1)/2;
if(cur<sum){
phigh++;
}
if(cur==sum){
vector<int> res;
for(int i=plow;i<=phigh;i++){
res.push_back(i);
}
allres.push_back(res);
plow++;
}
if(cur>sum){
plow++;
}
}
return allres;
}
};
