LeetCode 829 题 “连续整数求和” 要求：给定一个正整数 n，返回有多少组 连续正整数 的和等于 n。

✅ 核心思路（数学方法）

设这组连续正整数有 k 个，首项为 x，则这些数为：

x, x+1, x+2, …, x + k - 1

它们的和为等差数列求和：

text{sum} = frac{k(2x + k - 1)}{2} = n

两边乘 2：

k(2x + k - 1) = 2n

解出 x：

2x = frac{2n}{k} - k + 1

为了使 x 是 正整数，必须满足：

1. 2n % k == 0（即 k 是 2n 的约数）
2. (2n / k - k + 1) 是 正偶数

但其实我们不需要显式判断“正”，只要在枚举 k 时保证 k(k+1)/2 sqrt(2n)，则 k * (k+1)/2 > n，不可能成立。

✅ 推荐解法（简洁高效，O(√n)）

public int consecutiveNumbersSum(int n) {
int ans = 0;
// 枚举连续序列的长度 k
for (int k = 1; k * (k + 1) / 2 = 1

✅ 另一种等价写法（基于 2n 的因子）

public int consecutiveNumbersSum(int n) {
int ans = 0;
n *= 2;
for (int k = 1; k * k < n; k++) {
if (n % k == 0) {
// 检查 (n/k - k + 1) 是否为偶数
if ((n / k - k + 1) % 2 == 0) {
ans++;
}
}
}
return ans;
}

这种写法利用了 k 是 2n 的因子，并且 (2n/k - k + 1) 为偶数 ⇒ x 为整数。

✅ 示例验证

• n = 5

  • → k=1
  • → k=2
  • 输出：2 ✅

• n = 9

  • , , → 输出：3 ✅

• n = 15

  • , , , → 输出：4 ✅

⏱️ 复杂度

• 时间复杂度：O(√n)
• 空间复杂度：O(1)

适用于 n ≤ 1e9 的约束。

✅ 总结

最推荐使用第一种写法（基于 k(k+1)/2 <= n），逻辑清晰、边界自然、无需处理 2n 溢出问题（用 long 更安全，但 Java 中 k 较小时 k*(k+1)/2 不会溢出 int 对于 n ≤ 1e9）。

如需绝对安全，可改用 long 中间变量：

for (long k = 1; k * (k + 1) / 2 <= n; k++) {
if ((n - k * (k - 1) / 2) % k == 0) {
ans++;
}
}

但实际 k 最大约为 √(2×1e9) ≈ 44720，k*(k+1) 最大约 2e9，在 int 边界附近，建议用 long 避免溢出。

如有需要，我也可以提供 Python、C++ 或 Rust 版本。