LeetCode829. 连续整数求和

题目描述

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

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

示例1：

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

题解

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

(a+a+k−1)k2=n

得 (2a+k−1)k=2n，推出 k∣2n

再变形可得 2a=2nk−k+1，由 a∈x|x≥1∧x∈N 推出 2∣(2nk−k+1)

还能推出 2nk−k+1≥2，进而得到 2nk≥k+1>k，即 k<√2n

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

代码

cpp

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(√2n)

• 空间复杂度：O(1)