剑指offer_牛客_JZ41——和为S的连续正数序列（新的补充）

题目描述

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

返回值描述:

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

示例1

输入

返回值

[[2,3,4],[4,5]]

思路

方法四：按序列大小遍历

这道题我又想了一下，感觉上一篇文章方法三对a进行遍历还是不够快。因为如果sum为100的话，a要遍历50次。但事实上倒数第一个可能的a肯定小于50，因为两个数相加等于100，那a一定小于sum/2。倒数第二个可能的a肯定小于32，因为三个数相加等于100，那a一定小于sum/3-1。这样的话我只需要遍历到sum/n-(n-1)/2<1的时候就好。通过n+(n*n-n)/2 > sum解出n=14，相比50次要小很多。
在这个基础上，如果我们利用以下三个定理，就可以排除更多的选项。

当n为偶数时，n个连续的数相加一定不能被n除尽
当n为偶数时，n个连续的数相加再加n/2一定能被n除尽
当n为奇数时，n个连续的数相加一定能被n除尽

以100为例，整个遍历过程就是这样的：

1. 100可以被2整除，所以2个连续的数不可能加起来等于100
2. 100不可以被3整除，所以3个连续的数不可能加起来等于100
3. 100可以被4整除，所以4个连续的数不可能加起来等于100
4. 100可以被5整除，所以5个连续的数可能加起来等于100
    a = 100/5-(5-1)/2 = 18; b = a+n-1 = 22
5. 100+6/2不可以被6整除，所以6个连续的数不可能加起来等于100
6. 100不可以被7整除，所以7个连续的数不可能加起来等于100
7. 100+8/2可以被8整除，所以8个连续的数可能加起来等于100
    a = 100/8-(8-1)/2 = 9; b = a+n-1 = 16
8. 100不可以被9整除，所以9个连续的数不可能加起来等于100
9. 100可以被10整除，所以10个连续的数不可能加起来等于100
10. 100不可以被11整除，所以11个连续的数不可能加起来等于100
11. 100+12/2不可以被12整除，所以12个连续的数不可能加起来等于100
12. 100不可以被13整除，所以13个连续的数不可能加起来等于100
13. 100+14/2不可以被14整除，所以14个连续的数不可能加起来等于100

我觉得新的这个方法在数字特别大的时候可以更快地解决这个问题。

题解：

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
        for(int n=2;n+(n*n-n)/2<=sum;n+=1){
            int a,b;
            if(n%2==0 && (sum+n/2)%n == 0 || n&1 && sum%n == 0){
                a = sum/n - (n-1)/2;
                b = a+n-1;
                vector<int> temp;
                for(int i=a;i<=b;i++){
                    temp.push_back(i);
                }
                ans.push_back(temp);
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

实际运行效果

我对比了按序列大小遍历、一元二次求根、滑动窗口三个方法，发现按序列大小遍历果然是最快的方法。但是之前认为一元二次求根比滑动窗口快却是错的，目前还没弄清楚为什么，后续会继续探究，欢迎交流。

对照代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>

using namespace std;

class Solution1 {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
        for(int n=2;n+(n*n-n)/2<=sum;n+=1){
            int a,b;
            if(n%2==0 && (sum+n/2)%n == 0 || n&1 && sum%n == 0){
                a = sum/n - (n-1)/2;
                b = a+n-1;
                vector<int> temp;
                for(int i=a;i<=b;i++){
                    temp.push_back(i);
                }
                ans.push_back(temp);
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

class Solution2 {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
        for(int a=1;a<=sum/2;a++){
            double x = -1.0/2 + sqrt(1.0/4+4*(2*sum+a*a-a))/2;
            int b = round(x);
            if(b*b - a*a + a + b == 2*sum){
                vector<int> temp;
                for(int i=a;i<=b;i++){
                    temp.push_back(i);
                }
                ans.push_back(temp);
            }
        }
        return ans;
    }
};

class Solution3 {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //子序列和的最大值
        int End=sum/2+1;
        int left=1;
        int right=1;
        int CurSum=1;
        vector<vector<int> >res;
        while(left<=End-1&&right<=End)
        {
            if(CurSum==sum)
            {
                GetVector(res,left,right);
                right++;
                CurSum-=left;
                left++;
                CurSum+=right;
            }
            else if(CurSum<sum)//增加右边界
            {
                right++;
                CurSum+=right;
            }
            else
            {
                CurSum-=left;
                left++;
            }
        }
        return res;
    }
    void GetVector(vector<vector<int> >&res,int left,int right)
    {
        if(left==right)
        {
            return ;
        }
        vector<int>V;
        for(int i=left;i<=right;i++)
        {
            V.push_back(i);
        }
        res.push_back(V);
    }
};

int main(){
    Solution1 s1 = Solution1();
    Solution2 s2 = Solution2();
    Solution3 s3 = Solution3();
    vector<vector<int> > res;
    time_t first,second;
    first = time(NULL);
    for (int i=0;i<10000;i++)
        res = s1.FindContinuousSequence(100000);
    second = time(NULL);
    printf("s1(按序列大小遍历): %f seconds\n", difftime(second, first));
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res.size();j++)
            cout<<res[i][j]<<' ';
        cout<<endl;
    }
    first = time(NULL);
    for (int i=0;i<10000;i++)
        res = s2.FindContinuousSequence(100000);
    second = time(NULL);
    printf("s2(一元二次求根): %f seconds\n", difftime(second, first));
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res.size();j++)
            cout<<res[i][j]<<' ';
        cout<<endl;
    }
    first = time(NULL);
    for (int i=0;i<10000;i++)
        res = s3.FindContinuousSequence(100000);
    second = time(NULL);
    printf("s3(滑动窗口): %f seconds\n", difftime(second, first));
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res.size();j++)
            cout<<res[i][j]<<' ';
        cout<<endl;
    }
    
    return 0;
}

对照结果：

s1(按序列大小遍历): 0.000000 seconds
153 154 155 156 157 
738 739 740 741 742 
1531 1532 1533 1534 1535 
3988 3989 3990 3991 3992 
19998 19999 20000 20001 20002 
s2(一元二次求根): 5.000000 seconds
153 154 155 156 157 
738 739 740 741 742 
1531 1532 1533 1534 1535 
3988 3989 3990 3991 3992 
19998 19999 20000 20001 20002 
s3(滑动窗口): 3.000000 seconds
153 154 155 156 157 
738 739 740 741 742 
1531 1532 1533 1534 1535 
3988 3989 3990 3991 3992 
19998 19999 20000 20001 20002