梁越

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

0 人看过

前缀和、滑窗

题目描述

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

输出描述:

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

解法1:

滑窗算法:

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

temp<sum则右指针右移,temp>sum则左指针右移,temp=sum则push_back所有左指针到右指针元素
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

前缀和:

用两个循环,起点相同,

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

当temp>sum时,快指针回溯到慢指针,同时temp归0,重新进行上一步
链接: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;
    }
};