【剑指Offer】输入一个正数s，打印出所有和为s 的连续正数序列（序列大小至少为2）（C++）

87 阅读 0 评论 58 点赞

我是靠谱客的博主满意泥猴桃，这篇文章主要介绍【剑指Offer】输入一个正数s，打印出所有和为s 的连续正数序列（序列大小至少为2）（C++），现在分享给大家，希望可以做个参考。

题目用例：
s = 15，那么由于1+2+3+4+5 = 4+5+6＝7+8 = 15，所以存在3个这样的序列。
分析：
由于序列大小至少为2，我们定义两个变量l和r，分别表示序列的最小值和最大值。
对于r而言，r取何值其实是有一个范围的，即当序列只有2个数时，r的上限可以被确定，即：(r - 1) + r <= s
代码：

复制代码

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
#include <iostream>
using namespace std;

void printSubArray(int sum)
{
    int r = (sum + 1) / 2;  // 序列右端
    int l = r - 1;          // 序列左端
    int s = 0;              // 序列和

    if (l < 1)
        return;

    for (int i = l; i <= r; ++i)
        s += i;
    while (l > 0)
    {
        if (s == sum)
        {
            for (int i = l; i <= r; ++i)
                cout << i << " ";
            cout << endl;
            s -= r; --r;  // 减去一个大值后，至少要加上两个小值
            --l; s += l;
            --l; s += l;
        }   
        if (s > sum)
        {
            s -= r;
            --r;
        }
        if (s < sum)
        {
            --l;
            s += l;
        }
    }
}

int main()
{
    int sum;
    cout << "Enter sum: ";
    cin >> sum;
    printSubArray(sum);

    return 0;
}