剑指41-和为S的连续正整数序列

前缀和、滑窗

题目描述

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

输出描述:

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

解法1：

代码语言：javascript复制

滑窗算法：

定义两个指针，用一个temp记录当前和，

temp<sum则右指针右移，temp>sum则左指针右移，temp=sum则push_back所有左指针到右指针元素

代码语言：javascript复制

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        int l=1, r=1;
        int temp=0;
        while(l<=sum/2)
        {
            if(temp<sum){
                temp =r;
                r  ;
            }
            else if(temp>sum)
            {
                temp-=l;
                l  ;
            }
            else
            {
                vector<int> t;
                for(int i=l;i<r;i  )
                {
                    t.push_back(i);
                }
                res.push_back(t);
                t.clear();
                temp-=l;  //左指针右移
                l  ;
            }
        }

        return res;
    }
};

解法2

代码语言：javascript复制

前缀和：

用两个循环，起点相同，

相当于两个指针，快指针右移，同时计算总和，temp记录

当temp>sum时，快指针回溯到慢指针，同时temp归0，重新进行上一步

代码语言：javascript复制

链接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe?answerType=1&f=discussion
来源：牛客网

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        int tmp = 0;
        for (int i=1; i<=sum/2;   i) {
            for (int j=i; j<sum;   j) {
                tmp  = j;
                if (sum == tmp) {
                    vector<int> ans;
                    for (int k=i; k<=j;   k) ans.push_back(k);
                    ret.push_back(ans);
                }
                else if (tmp > sum) {
                    // 提前剪枝
                    tmp = 0;
                    break;
                }
            }
        }
        return ret;
    }
};

数学

0 人点赞