LeetCode 829. 连续整数求和
题目描述
题意分析
将给定正整数
n表示成若干个连续正整数之和，统计不同表示的数量。每段至少包含一个数，所以只包含n自身也算一种；首项必须大于零，不允许从零或负数开始。只需返回方案数，不需要列出序列。一个方案由首项和长度共同确定，可以固定其中一个条件，再推导另一个是否存在。
解法：枚举长度
核心思路
[!blue]
固定序列长度为
k、首项为x，这段连续数就是从x逐个加一得到。把每项中的x单独提出来，总和可以写成n = k * x + k * (k - 1) / 2，其中后一部分是从零到k - 1的递增偏移总和。令
remain = n - k * (k - 1) / 2，则首项只能是remain / k。只要remain > 0且能够被k整除，这个首项就一定是正整数；每个长度至多产生一个方案，所以满足时答案加一即可，无需再枚举起点。代码在递增偏移严格小于
n时继续枚举，直接保证了remain > 0。这个条件比按最小首项为一推导出的最紧长度上界稍宽，但多出来的长度不会产生错误答案：如果正的剩余量能整除正数k，商至少为一；不能整除就被检查排除。随着长度增大，递增偏移单调增加。一旦它不小于
n，当前以及后面更长的序列都不可能有正首项，可以直接结束。偏移按长度平方增长，因此总共只需尝试根号级别的长度；乘法使用 64 位整数，避免在相除之前发生溢出。
解题步骤
- 从长度
k = 1开始，初始化方案数为零。- 只要
k * (k - 1) / 2 < n，就计算剩余量remain。- 若
remain % k == 0，说明这个长度对应一个唯一合法的正首项，方案数加一。- 增加长度，直到正首项已不可能存在，返回方案数。
代码实现
class Solution {
public int consecutiveNumbersSum(int n) {
int answer = 0;
for (long k = 1; k * (k - 1) / 2 < n; k++) {
long remain = n - k * (k - 1) / 2;
// 剩余量为正且整除长度，就确定唯一正整数首项
if (remain % k == 0) {
answer++;
}
}
return answer;
}
}
func consecutiveNumbersSum(n int) int {
answer := 0
for k := int64(1); k*(k-1)/2 < int64(n); k++ {
remain := int64(n) - k*(k-1)/2
// 剩余量为正且整除长度，就确定唯一正整数首项
if remain%k == 0 {
answer++
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(\sqrt n)$，循环中的二次偏移必须小于
n，每个候选长度只做常数次运算。- 空间复杂度：$O(1)$，只保存长度、剩余量和答案。
关键点总结
[!green]
- 固定长度后，首项已经由求和公式唯一确定，不再需要逐个尝试。
- 正剩余量与整除条件共同保证首项是正整数。
- 偏移随长度单调增长，首次无法保持正剩余量时就能结束整个枚举。
- 长度一必须纳入统计，它对应原整数自身。
易错点总结
[!yellow]
- 从长度二开始，会漏掉单个整数这一种合法表示。
- 允许剩余量为零，会把从零开始的序列误算进去。
- 只判断能否整除而不限制正剩余量，会接纳零或负首项。
- 使用
k * (k + 1) / 2作为偏移，却仍按当前首项公式计算，混淆了从零和从一累加的定义。- 在窄整数类型中先完成乘法再转宽类型，不能避免中间乘积已经溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 57 - II. 和为s的连续正数序列 | 简单 | 同样利用连续正整数求和公式；Offer57-II要求每段至少两个数并输出序列，本题允许单个数n作为一种方案，只统计方案数，不能照搬从长度2开始的边界。 |
| 441. 排列硬币 | 简单 | 同样利用连续整数和的三角数结构，本题还需满足剩余量能按长度整除且起点为正。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！