参考资料:
[1]renhao426的回答:
https://www.nowcoder.com/profile/4885081/codeBookDetail?submissionId=17420960
思路:
整体思路:如果总和数小,big++,使得数变大, 如果数大,small++,使得数变小,得到之后,big++
自己的解法:
class Solution {
public:
int AddFromSmallToBig(int nNum1, int nNum2)
{
return (nNum1 + nNum2)*(nNum2 - nNum1 + 1) / 2;
}
vector<vector<int>> FindContinuousSequence(int sum)
{
vector<vector<int>> vecResult;
if (sum < 3)
return vecResult;
int nSmall = 1, nBig = 2;
while (nSmall < (1 + sum) / 2)
{
int nTmp = AddFromSmallToBig(nSmall,nBig);
if (nTmp < sum)
nBig++;
else if (nTmp > sum)
nSmall++;
else
{
vector<int> vecResult1;
vecResult1.clear();
for (int i = nSmall; i <= nBig; i++)
{
vecResult1.push_back(i);
}
vecResult.push_back(vecResult1);
nBig++;
}
}
return vecResult;
}
};
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
//整体思路:如果总和数小,big++,使得数变大, 如果数大,small++,使得数变小
int small=1;
int big =2;
//其中一个值
vector<int> result1;
vector<vector<int> >result;
while(small<=(sum/2))//因为至少两个数
{
int temp = SumFromSmallToBig(small,big);
if(temp<sum)
big++;
else if(temp>sum)
small++;
else
{
for(int i = small;i<=big;i++)
{
result1.push_back(i);
}
result.push_back(result1);
result1.clear();//肯定得清空
big++;//不然就得到一个数
}
}
return result;
}
int SumFromSmallToBig(int small, int big)
{
return (small+big)*(big-small+1)/2;
}
};
标准答案:
class Solution {
public:
//从small到big的求和
int SumFromSmallToBig(int small,int big)
{
int sum =0;
/*
for(int i= small;i<=big;i++)
{
sum+=i;
}
*/
/*
另一种求和思路。
1+2+3+4+...+n
n+.........+1
(1+n)*n/2
*/
sum = (small+big)*(big-small+1)/2;
return sum;
}
vector<vector<int> > FindContinuousSequence(int sum) {
//本题的思路:
//初始化small=1,big =2;
//small到big的序列的和大于sum,small++,小于sum,big++;
//small要小于(1+sum)/2
//如果等于的话,接下来是big++
int small = 1;
int big = 2;
int i=0;
vector<int> sequence;
vector<vector<int> > sequence_set;
while(small<(1+sum)/2)
{
if(SumFromSmallToBig(small,big)<sum)
big++;
else if(SumFromSmallToBig(small,big)>sum)
small++;
else if((SumFromSmallToBig(small,big) == sum))
{
for(i=small;i<=big;i++)
{
sequence.push_back(i);
}
sequence_set.push_back(sequence);
sequence.clear();//要注意清空!!!
big++;
}
}
return sequence_set;//要注意return
}
};