和为S的连续整数序列

86 阅读 0 评论 57 点赞

我是靠谱客的博主舒心花卷，最近开发中收集的这篇文章主要介绍和为S的连续整数序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1，题目要求

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

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

2，题目思路

对于这道题，要求找到所有和为S的连续正数序列。

这道题中，基础的序列是1、2、3、4的形式。
因此，在寻找的过程中，假如说我们设定序列中的最小值为small，最大值为big，那么，small的最大值为 (1+sum)/2。

同时，要求连续的数字不能重复，因此，如果S<3，一定找不到这样的序列。

在问题的解决上，我们通过small和big设定一个窗口，计算窗口内的和。
根据窗口的和：

如果当前窗口内的值小于sum，那么右边窗口右移一下；
如果当前窗口内的值大于sum，那么左边窗口右移一下；

3，代码实现

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        if(sum<3)
            return {};
        vector<vector<int>> res;
        int mid = (1+sum)/2;
        int pLow = 1, pHigh = 2;
        while(pLow < mid){
            int currSum = (pLow+pHigh)*(pHigh-pLow+1)/2;
            if(currSum == sum){
                vector<int> tmp;
                for(int i = pLow;i<=pHigh;i++)
                    tmp.push_back(i);
                res.push_back(tmp);
                pLow++;
            }
            else if(currSum < sum)
                pHigh++;
            else
                pLow++;
        }
        return res;
    }
};