连续正整数和

题意

给定一个正整数 M，输出所有连续正整数段 [l,r]，满足：

l < r，也就是至少包含两个数；
$l + (l+1) + ... + r = M$ 。

要求按左端点从小到大输出所有解。

思路

先看一个直接枚举的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll m;
    cin >> m;

    for (ll left_pos = 1; left_pos <= m / 2; ++left_pos) {
        ll sum = 0;
        for (ll right_pos = left_pos; right_pos <= m; ++right_pos) {
            sum += right_pos;
            if (sum == m && right_pos > left_pos) {
                cout << left_pos << ' ' << right_pos << '\n';
            }
            if (sum >= m) {
                break;
            }
        }
    }

    return 0;
}

朴素做法枚举左端点 l，再不断枚举右端点 r 并累加。
因为所有数都是正整数，当当前和已经大于等于 M 时，再继续扩大右端点只会让和更大，所以可以停止当前左端点的枚举。

这个性质还可以继续优化成双指针。

维护一个窗口 [left_pos, right_pos] 和当前区间和 sum：

如果 sum < M，说明当前区间太小，需要右端点右移，把更大的数加进来。
如果 $sum >= M$ ，说明当前区间已经够大：
- 若 $sum == M$ 且长度至少为 2，输出答案；
- 然后左端点右移，把最左边的数移出去。

因为 left_pos 和 right_pos 都只会向右移动，所以总复杂度是线性的。

窗口移动过程

这张表用目标和 15 展示窗口如何移动。

窗口	区间和	操作
`[1,1]`	1	太小，右端点右移
`[1,5]`	15	输出 `1 5`，左端点右移
`[2,5]`	14	太小，右端点右移
`[4,6]`	15	输出 `4 6`，左端点右移
`[7,8]`	15	输出 `7 8`，左端点右移

可以看到，窗口和小了就向右扩，大了或等于目标就从左边缩。
这个过程正是同向双指针的典型模型，也可以参考 rbook 的同向双指针旧页。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll m;
    cin >> m;

    ll left_pos = 1;
    ll right_pos = 1;
    ll sum = 1;

    while (left_pos <= m / 2) {
        if (sum < m) {
            ++right_pos;
            sum += right_pos;
        } else {
            if (sum == m && right_pos > left_pos) {
                cout << left_pos << ' ' << right_pos << '\n';
            }
            sum -= left_pos;
            ++left_pos;
        }
    }

    return 0;
}

复杂度

left_pos 和 right_pos 都只单调右移。
时间复杂度 $O(M)$ 。
只维护几个变量，空间复杂度 $O(1)$ 。

总结

这题的关键是利用“正整数”带来的单调性。
如果当前区间和太小，只能扩大右端点；如果当前区间和已经够大，就应该移动左端点。
这种单调窗口问题就是双指针最适合处理的场景。

目录

题意

思路

窗口移动过程

代码

复杂度

总结