ZYF007 连续自然数和
大约 3 分钟
ZYF007 连续自然数和
【算法】 双指针、数学
【C++】 双指针
【难度】 普及-
一、题目简述
给定一个正整数 (),要求找出所有连续正整数段(至少包含 2 个数),使得这些数的和恰好等于 。按段的起始数从小到大的顺序输出每一段。
例如 时,输出:
2 4
4 5表示 ,。
二、解题思路
算法选择:双指针(滑动窗口)
我们需要在正整数序列 上找一个连续子段,使得元素之和等于 。因为要找所有解,暴力枚举起点和终点是 的,对于 来说太慢了。
双指针法:维护一个窗口 ,窗口内的元素和为 。
- 当 时,扩展右边界:
r++,sum += r。 - 当 时,收缩左边界:
sum -= l,l++。 - 当 时,记录答案,然后收缩左边界继续找:
sum -= l,l++。
为什么双指针是正确的?因为当 时,只有收缩左边界才能让和变小(扩展右边界只会更大);当 时,只有扩展右边界才能让和变大。这是典型的"滑动窗口"在单调递增序列上的应用。
边界分析
最多到多少?至少两个数,如果从 开始,最小的一段是 。要使得 ,有 。因此 最多到 , 也最多到 。
手动模拟
以 为例:
| 步骤 | l | r | sum | 比较 | 操作 |
|---|---|---|---|---|---|
| 初始 | 1 | 2 | 3 | 3 < 9 | r=3, sum=6 |
| 1 | 1 | 3 | 6 | 6 < 9 | r=4, sum=10 |
| 2 | 1 | 4 | 10 | 10 > 9 | sum-=l, l=2, sum=9 |
| 3 | 2 | 4 | 9 | 9 == 9 | 输出 2 4,sum-=l, l=3, sum=7 |
| 4 | 3 | 4 | 7 | 7 < 9 | r=5, sum=12 |
| 5 | 3 | 5 | 12 | 12 > 9 | sum-=l, l=4, sum=9 |
| 6 | 4 | 5 | 9 | 9 == 9 | 输出 4 5,sum-=l, l=5, sum=5 |
| 7 | 5 | 5 | 5 | 5 < 9 | r=6, sum=11 |
| ... | ... | ... | ... | l >= r 或 r 越界 | 结束 |
输出为 2 4 和 4 5。
再以 为例:
| l | r | sum | 操作 |
|---|---|---|---|
| 1 | 5 | 15 | 输出 1 5(1+2+3+4+5=15) |
| 4 | 6 | 15 | 输出 4 6(4+5+6=15) |
| 7 | 8 | 15 | 输出 7 8(7+8=15) |
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long long M;
cin >> M;
long long l = 1, r = 2, sum = 3; // 初始窗口 [1, 2],和为 3
// l < r 保证至少两个数;r <= M/2+1 是上界
while (l < r && r <= M / 2 + 1) {
if (sum < M) {
r++;
sum += r;
} else if (sum > M) {
sum -= l;
l++;
} else { // sum == M
cout << l << " " << r << endl;
sum -= l;
l++;
}
}
return 0;
}四、复杂度分析
- 时间复杂度: 最坏情况。但实际上 不会超过 ,且每个数最多进入和离开窗口一次,因此实际运行效率很高。对于 ,在 C++ 中完全可以接受。
- 空间复杂度:,只用了几个变量。
知识扩展:数学方法
本题也可以用等差数列求和公式求解。设连续段从 到 ,共 个数,和为:
但双指针方法更直观易懂,且代码简洁。
易错点
- 段至少包含 2 个数,所以循环条件要确保 。
- 当 输出后,别忘了收缩左边界继续找下一组解。
- 用
long long避免求和时溢出( 最大 ,实际上int也够,但养成好习惯)。
