和为S的连续正数序列

101 阅读 0 评论 67 点赞

我是靠谱客的博主俊逸猫咪，这篇文章主要介绍和为S的连续正数序列，现在分享给大家，希望可以做个参考。

题目
输入一个正整数S，打印出所有和为S的连续序列，至少包含两个数。
例如输入15，则1，2，3，4，5和4，5，6和7，8都是结果序列。

算法：
因为所求序列是连续的递增序列，所以需要前后指针包含的是连续的数据。
Big指针在前，当和小于target时继续向前增加数字；small在后，当和大于target时向前减少数字。

边界条件：因为结果数组必须包含两个数字以上，所以small<(s+1)/2，比如target为15，small不能到8，因为big至少为9超过了target。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(sum < 3)
            return res;
        int small = 1;
        int big = 2;
        //累加指针之间所有值
        int calculate = small + big;
        //边界条件,small不能超过sum的一半
        while (small < (1+sum)/2){
            //相等,则保存结果,并让big继续向前
            if(calculate == sum){
                vector<int>line;
                for (int i = small; i <= big ; ++i) {
                    line.push_back(i);
                }
                res.push_back(line);
                calculate += ++big;
            }
                //小于,则继续增加指针之间数
            else if(calculate<sum)
                calculate += ++big;
            //大于.则减少数
            else
                calculate -= small++;
        }
        return res;
    }
};