LeetCode 829. 连续整数求和

2025-03-31 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 829. 连续整数求和

题意分析

题目问一个正整数 $n$ 有多少种方式可以写成若干个连续正整数之和。这里的「若干个」包含 1，也就是说 $n$ 自己就算一种方案；组成序列的每一项都必须是正整数，不允许出现 0 和负数。

要数的是方案数，不是把方案列出来，这提示答案很可能有闭式的判定条件，不必真的枚举序列。

约束里 $n$ 最大到 $10^9$。这个量级排除了一切与 $n$ 同阶的做法——无论是逐个枚举起点，还是滑动窗口在 $[1, n]$ 上扫，都会超时。能接受的复杂度大致在 $O(\sqrt{n})$ 或 $O(\log n)$ 这一档，这本身就是「要用数学而不是枚举元素」的强烈信号。

边界上要留意：长度为 1 的方案必须计入，漏掉它答案会整体少 1；序列首项必须至少是 1，所以推导出的首项要检查是否为正整数；$n$ 可以取到 1，此时唯一方案就是它自己。

解法：枚举长度

核心思路

暴力做法是枚举连续序列的起点和终点，用前缀和判断区间和是否等于 $n$。即使用双指针优化成线性，$n$ 到 $10^9$ 时也完全跑不动，何况序列可能很长。

瓶颈在于我们在「元素」这个维度上枚举，而元素的数量就是 $n$ 本身。换一个维度：一个连续正整数序列由首项 $x$ 和长度 $k$ 两个参数唯一确定，与它落在数轴的哪一段无关。用等差数列求和把约束写出来：
\[n = x + (x+1) + \dots + (x+k-1) = kx + \frac{k(k-1)}{2}\]
这个式子的价值在于，一旦把 $k$ 固定下来，$x$ 就被完全解出：$x = \dfrac{n - k(k-1)/2}{k}$。也就是说，每个长度 $k$ 至多对应一种方案，方案是否存在只取决于这个 $x$ 是不是正整数。于是数方案数等价于数「有多少个 $k$ 能让 $x$ 合法」，枚举维度从元素换成了长度。

记 $\text{remain} = n - k(k-1)/2$，合法条件是 $\text{remain} > 0$ 且 $k \mid \text{remain}$。这两条其实已经蕴含了 $x \geq 1$：整除意味着 $\text{remain}$ 是 $k$ 的倍数，而它又为正，所以至少是 $k$，于是 $x = \text{remain}/k \geq 1$，首项自动是正整数，不需要额外检查。

最后确定枚举范围。长度为 $k$ 的序列，其最小可能的和是 $1 + 2 + \dots + k = k(k+1)/2$，一旦这个下界超过 $n$，更长的序列就再也凑不出 $n$ 了。用代码里的 $\text{remain} > 0$ 作为循环条件是等价而更省事的写法：$\text{remain} = n - k(k-1)/2 > 0$ 恰好刻画了「去掉递增偏移之后还有剩余可以分配给首项」。由此 $k$ 的上界是 $O(\sqrt{n})$ 量级，对 $n = 10^9$ 大约只需枚举四万多次。

于是不变量很清晰：循环进行到长度 $k$ 时，answer 恰好等于「所有长度不超过 $k-1$ 的合法方案数」；每一轮只做一次减法和一次取余，判断长度为 $k$ 的方案是否存在。

解题步骤

令 answer = 0，从长度 $k = 1$ 开始枚举。为什么必须从 1 起步：长度为 1 的序列就是 $n$ 自己，题目把它算作一种合法方案，从 2 开始会整体少算一种。

循环条件取 $k(k-1)/2 < n$，也就是 remain 仍为正。为什么这样就够：这等价于「长度 $k$ 的序列至少要用掉的递增偏移量还没吃满 $n$」，一旦不成立，更大的 $k$ 只会更糟，可以安全终止；这也把枚举次数压到了 $O(\sqrt{n})$。

每轮计算 remain = n - k * (k - 1) / 2。为什么减的是 $k(k-1)/2$ 而不是 $k(k+1)/2$：把序列写成 $x, x+1, \dots, x+k-1$ 时，相对首项的偏移量之和是 $0 + 1 + \dots + (k-1) = k(k-1)/2$，多减一层会让首项整体错位。

若 remain % k == 0，answer 加一。为什么整除就说明方案存在：此时 $x = \text{remain}/k$ 是整数，配合 remain 为正可推出 $x \geq 1$，于是从 $x$ 开始的 $k$ 个连续正整数之和恰好是 $n$；反之若不整除，则不存在整数首项，这个长度无解。

中间量用 64 位整型保存。为什么：$k$ 可以逼近 $\sqrt{2n} \approx 4.5 \times 10^4$，乘积 $k(k-1)$ 逼近 $2 \times 10^9$，已经越过 32 位有符号整数的上界。

枚举结束返回 answer。

以 n = 9 走一遍：answer 初值 0。

$k = 1$：偏移量 $1 \times 0 / 2 = 0$，小于 9，进入循环。remain $= 9 - 0 = 9$，$9 \bmod 1 = 0$，成立，answer 变成 1。对应首项 $x = 9$，序列是 $[9]$。

$k = 2$：偏移量 $2 \times 1 / 2 = 1 < 9$。remain $= 9 - 1 = 8$，$8 \bmod 2 = 0$，成立，answer 变成 2。对应 $x = 4$，序列是 $[4, 5]$，求和 9，正确。

$k = 3$：偏移量 $3 \times 2 / 2 = 3 < 9$。remain $= 9 - 3 = 6$，$6 \bmod 3 = 0$，成立，answer 变成 3。对应 $x = 2$，序列是 $[2, 3, 4]$，求和 9，正确。

$k = 4$：偏移量 $4 \times 3 / 2 = 6 < 9$。remain $= 9 - 6 = 3$，$3 \bmod 4 = 3 \neq 0$，不成立，answer 保持 3。这说明不存在四个连续正整数之和为 9（$1+2+3+4 = 10$ 已经超了）。

$k = 5$：偏移量 $5 \times 4 / 2 = 10$，不小于 9，循环终止。

返回 3，即 $9 = 9 = 4 + 5 = 2 + 3 + 4$，与预期一致。

再用 n = 15 复核一次：$k = 1$ 时 remain 为 15 整除成立；$k = 2$ 时 remain 为 14，$14 \bmod 2 = 0$ 成立（$7 + 8$）；$k = 3$ 时 remain 为 12，整除成立（$4 + 5 + 6$）；$k = 4$ 时 remain 为 9，$9 \bmod 4 = 1$ 不成立；$k = 5$ 时 remain 为 5，整除成立（$1+2+3+4+5$）；$k = 6$ 时偏移量 15 不小于 15，终止。答案为 4，正确。

代码实现

class Solution {
    // 只要 n - k\(k-1)/2 为正且能被 k 整除，就存在解。
    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 {
    // 只要 n - k\(k-1)/2 为正且能被 k 整除，就存在解。
    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})$，循环条件 $k(k-1)/2 < n$ 把 $k$ 的上界限制在 $\sqrt{2n}$ 附近，每一轮只做常数次乘法、减法和取余；$n = 10^9$ 时约四万五千轮，远在时限之内。

空间复杂度：$O(1)$，只用了 answer、k、remain 三个标量，不随 $n$ 增长。

关键点总结

当枚举的维度和数据规模同阶时，换一个维度枚举。这里把「枚举序列的起点」换成「枚举序列的长度」，规模立刻从 $n$ 降到 $\sqrt{n}$。

用参数化的方式重述对象：连续正整数序列由首项和长度两个参数唯一决定，写出求和公式后，固定一个参数就能解出另一个，判定随之退化成一次整除检查。

「至多一个解」这个性质要显式确认。正因为每个长度最多对应一个首项，方案数才等于合法长度的个数，否则还得再乘上每个长度下的方案数。

有些边界条件是被其它条件蕴含的。这里 $\text{remain} > 0$ 加上整除已经保证首项至少为 1，写多余的检查不算错，但能看出是否真的推导过。

面试视角：这题的正解只有五行，分数几乎全在推导上。把 $n = kx + k(k-1)/2$ 当场写出来并说明每一项的来历，比直接抛结论更有说服力。

面试视角：可以主动给出结论性的另一解——答案恰好等于 $n$ 的奇因子个数。把 $n$ 分解成 $2^a \cdot m$（$m$ 为奇数），答案就是 $m$ 的因子个数，复杂度同样是 $O(\sqrt{n})$ 但常数更小。能说出这条数论结论并简述来源，是明显的加分项。

易错点总结

错误写法：从 $k = 2$ 开始枚举，认为「一个数不算连续整数之和」。用例 n = 9 → 漏掉 $[9]$ 这一种，返回 2，正确答案是 3。

错误写法：偏移量记成 $k(k+1)/2$。用例 n = 15 → $k = 5$ 时 remain 变成 0 并被循环条件挡在外面，漏掉 $1+2+3+4+5$ 这一种，返回 3，正确答案是 4。

错误写法：循环条件放宽成 $k \leq n$ 之类，只检查整除而不保证 remain 为正。用例 n = 9 → $k = 9$ 时 remain 为 $-27$，而 $-27 \bmod 9 = 0$ 同样成立，凭空多计一种非法方案，答案偏大。

错误写法：循环条件写成 $k \leq n$ 且中间量正确。用例 n = 1000000000 → 需要迭代十亿次，直接超时。

错误写法：用 32 位整型保存 $k(k-1)/2$。用例 n = 1000000000 → $k$ 逼近 $4.5 \times 10^4$ 时 $k(k-1)$ 接近 $2 \times 10^9$ 越过 int 上界变成负数，循环条件恒成立并陷入错误的长循环。

错误写法：循环条件误用 $\leq$，允许 remain 等于 0。用例 n = 3 → $k = 3$ 时 remain 为 0 且被 3 整除，对应首项 $x = 0$ 的序列 $[0,1,2]$，但 0 不是正整数，返回 3，正确答案是 2。

错误写法：把结论记成「答案等于 $n$ 的因子个数」。用例 n = 12 → 因子有 1、2、3、4、6、12 共 6 个，返回 6，正确答案是 2（只有奇因子 1 和 3 计数，对应 $[12]$ 与 $3+4+5$）。

错误写法：改用双指针在 $[1, n]$ 上滑动窗口求和。用例 n = 1000000000 → 窗口要扫过十亿个数，时间和溢出风险双双失控。

相似题目

题目	难度	考察点
172. 阶乘后的零	中等	同为公式推导题，靠计数因子 5 的个数避开阶乘运算
204. 计数质数	中等	数论计数，用筛法而非逐个判定，优化的是常数与筛序
560. 和为 K 的子数组	中等	同为区间和计数，但元素任意，只能靠前缀和哈希
1201. 丑数 III	中等	计数结合容斥与二分，同样在答案空间而非元素上求解