题解 | 数学思路，复杂度为根号n。#和为S的连续正数序列#
和为S的连续正数序列
http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
偏数学思路
看大家都在双指针滑动窗口，要么就是遍历。
提供一个偏数学的思路。十行代码解决问题，复杂度为)
。
等差数列的数字个数为n，起始数字为a，
主要思路是在合适范围内遍历n，然后求解a判断是否为整数，若为整数则ok。
代码如下，具体公式推导在后边。
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
double n =int(0.5+sqrt(2*sum+1/4));//数列长度上限
vector<vector<int>> res;
while(n>1){
if(sum/n+(1-n)/2 - int(sum/n+(1-n)/2)==0){//判断计算结果为整数，sum/n+(1-n)/2表示的是数列第一个数字。
vector<int> res_unit(n);//其中一种结果
iota(res_unit.begin(),res_unit.end(),sum/n+(1-n)/2);//生成一个起始为sum/n+(1-n)/2，长度为n的数列。
res.push_back(res_unit);}//所有的结果
n--;}
return res;}};
公式推导
设等差数列的数字个数为n，起始数字为a，其和为sum，则满足
可以得到
其中在本题定义域内，n是a的减函数，取a = 1，可得
可以将n的范围确定下来，大概在2和
之间，复杂度为
级别。
接下来遍历n,求解a
若a为整数，则是一种合格的情况。
投递卓越教育等公司8个岗位 >
