LeetCode829. 连续整数求和

题目描述

本题目来自LeetCode上的『829.连续整数求和』

给定一个正整数 n，返回连续正整数满足所有数字之和为 n 的组数 。

示例1：

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

题解

设这组连续的数字的首个数字为 $a$，长度为 $k$，则由等差数列和可知

$$\frac{(a+a+k-1)k}{2}=n$$

得 $(2a+k-1)k=2n$，推出 $k\mid 2n$

再变形可得 $2a=\frac{2n}{k}-k+1$，由 $a\in {x|x\ge 1\wedge x\in N}$ 推出 $2\mid (\frac{2n}{k}-k+1)$

还能推出 $\frac{2n}{k}-k+1\ge2$，进而得到 $\frac{2n}{k}\ge k+1>k$，即 $k<\sqrt{2n}$

综上，我们枚举 $k$，检查是否符合上述两个整除关系即可。

代码

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int limit = sqrt(n * 2);
        int ans = 0;
        for (int i = 1; i <= limit; ++i) {
            if (n * 2 % i != 0) {
                continue;
            }
            if ((2 * n / i - i + 1) % 2 == 0) {
                ++ans;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(\sqrt{2n})$

• 空间复杂度：$O(1)$