1.题目

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

来源：剑指offer

链接：/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

2.我的题解

先举个例子：

100可以分解为{18,19,20,21,22}，{9,10,11,12,13,14,15,16}；我们观察每个每个序列的中位数，可以发现：

序列长度乘以序列中位数等于被分解的数。

由中位数和序列长度可以推出整个序列。

尝试通过序列长度以及中位数的某些性质来判断序列是否合法。序列长度i为奇数：需满足sum%i==0；即中位数应是整数，才有可能形成序列；序列长度i为偶数：需满足sum%i!=0 && sum%(i>>1)==0；即中位数的小数部分是0.5；当然还有其他序列本身的限制：

序列的第一个数要大于0（正整数序列）；

序列的长度最小为2，最大为sum；

class Solution {vector<vector<int> >res;vector<int> tmp;public:vector<vector<int> > FindContinuousSequence(int sum) {res.clear();for(int i=sum;i>1;i--){tmp.clear();if(i&1 && sum%i==0 && (sum/i-i/2)>0){//oddfor(int j=-i/2;j<=i/2;j++)tmp.push_back((sum/i)+j);res.push_back(tmp);}else if((i&1)==0 && (sum%i!=0) &&(sum%(i>>1))==0 &&(sum*1.0/i-(i-1)/2.0)>0){//evenfor(double j=-(i-1)/2.0;j<=(i-1)/2.0;j+=1)tmp.push_back((sum*1.0/i)+j);res.push_back(tmp);}}return res;}};

两种情况可以合并：

class Solution {vector<vector<int> >res;vector<int> tmp;public:vector<vector<int> > FindContinuousSequence(int sum) {res.clear();for(int i=sum;i>1;i--){tmp.clear();if((i&1 && sum%i==0 && (sum/i-i/2)>0)||//odd((i&1)==0 && (sum%i!=0) &&(sum%(i>>1))==0 &&(sum*1.0/i-(i-1)/2.0)>0)){//evenfor(double j=-(i-1)/2.0;j<=(i-1)/2.0;j+=1)tmp.push_back((sum*1.0/i)+j);res.push_back(tmp);}}return res;}};

3.别人的题解

3.1 方法2的优化

序列的长度最长不会到达sum，最长的序列应该从1起，(1+n)n/2<sum得到n<sqrt(2S)；i为偶数，sum/i的小数部分为0.5可以优化为：(sum%i)*2=i；小数为0.5意味着取余后剩下一半。甚至还包含了i为偶数。时间复杂度：O(sqrt(n))

class Solution {vector<vector<int> >res;vector<int> tmp;public:vector<vector<int> > FindContinuousSequence(int sum) {res.clear();for(int i=sqrt(2*sum);i>1;i--){tmp.clear();if((i&1 && sum%i==0)||//odd(sum%i)*2==i){//evenfor(double j=-(i-1)/2.0;j<=(i-1)/2.0;j+=1)tmp.push_back((sum*1.0/i)+j);res.push_back(tmp);}}return res;}};

3.2 双指针法

从1开始，使用low和high确定一个序列，判断当前序列的和是否等于要求的值，等于则将当前序列加入结果，同时两个指针右移，更新当前序列和；当前序列的和小于要求的值：high后移，更新当前序列和；当前序列的和大于要求的值：low后移，更新当前序列和；每次仅操作序列的两端，相当于“滑动窗口”，因此可以利用上次的序列和更新当前序列和；

class Solution {vector<vector<int> >res;vector<int> tmp;public:vector<vector<int> > FindContinuousSequence(int sum) {res.clear();int low=1,high=2,total=3;while(low<=sum/2){if(total==sum){vector<int> tmp;for(int i=low;i<=high;i++)tmp.push_back(i);res.push_back(tmp);total+=(++high)-(low++);}else if(total<sum)total+=(++high);else total-=(low++);}return res;}};

4.总结与反思

（1）双指针法；

（2）判断两数相除结果的小数部分是否是0.5；