剑指Offer(牛客版)--面试题57(2): 和为 s 的连续正整数序列

84 阅读 0 评论 56 点赞

我是靠谱客的博主震动发卡，这篇文章主要介绍剑指Offer(牛客版)--面试题57(2): 和为 s 的连续正整数序列，现在分享给大家，希望可以做个参考。

题目描述：

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

分析：

完整代码：

复制代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //声明一个二位数组容器
        vector<vector<int>> data;
        //检查输入的合法性
        if(sum < 3)
            return data;
        //声明两个变量，分别表示序列的头部数字和尾部数字
        int small = 1;
        int big = 2;
        //声明一个变量表示总之条件
        int middle = (1 + sum) / 2;
        //声明一个变量表示当前的序列和
        int CurrSum = small + big;
        //如果头部数字没有超过 middle
        while(small < middle)
        {
            //如果当前的序列和等于 sum
            if( CurrSum == sum)
            {
                //将两个数字压入到容器中
                InsertNum(data, small, big);
            }
            //如果当前的序列和大于 sum 且 small 小于 middle
            while(CurrSum > sum && small < middle)
            {
                //更新当前的序列和
                CurrSum -= small;
                small++;//将 small 向后移动
                //如果当前的序列和等于 sum
                if(CurrSum == sum)
                {
                    //将两个数字间的序列压入到容器中
                    InsertNum(data, small, big);
                }
            }
            //如果当前的序列和小于 sum 
            big++;//big 往后移动
            CurrSum += big;
        }
        return data;
    }
private:
    //将两个数字间的序列压入到容器中
    void InsertNum(vector<vector<int>> &data, int small, int big)
    {
        //声明一个容器
        vector<int> array;
        //遍历两个数字之间的序列
        for(int i = small; i <= big; i++)
        {
            //将两个数字之间的数字压入到容器
            array.push_back(i);
        }
        data.push_back(array);
    }
};

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //声明一个二位数组容器
        vector<vector<int>> data;
        //检查输入的合法性
        if(sum < 3)
            return data;
        //声明两个变量，分别表示序列的头部数字和尾部数字
        int small = 1;
        int big = 2;
        //声明一个变量表示总之条件
        int middle = (1 + sum) / 2;
        //声明一个变量表示当前的序列和
        int CurrSum = small + big;
        //如果头部数字没有超过 middle
        while(small < middle)
        {
            //如果当前的序列和等于 sum
            if( CurrSum == sum)
            {
                //将两个数字压入到容器中
                InsertNum(data, small, big);
            }
            //如果当前的序列和大于 sum 且 small 小于 middle
            while(CurrSum > sum && small < middle)
            {
                //更新当前的序列和
                CurrSum -= small;
                small++;//将 small 向后移动
                //如果当前的序列和等于 sum
                if(CurrSum == sum)
                {
                    //将两个数字间的序列压入到容器中
                    InsertNum(data, small, big);
                }
            }
            //如果当前的序列和小于 sum 
            big++;//big 往后移动
            CurrSum += big;
        }
        return data;
    }
private:
    //将两个数字间的序列压入到容器中
    void InsertNum(vector<vector<int>> &data, int small, int big)
    {
        //声明一个容器
        vector<int> array;
        //遍历两个数字之间的序列
        for(int i = small; i <= big; i++)
        {
            //将两个数字之间的数字压入到容器
            array.push_back(i);
        }
        data.push_back(array);
    }
};