每日算法系列【LeetCode 829】连续整数求和

题目描述

给定一个正整数 N ，试求有多少组连续正整数满足所有数字之和为 N ?

示例1

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

示例2

输入：
9
输出：
3
解释：
9 = 9 = 4 + 5 = 2 + 3 + 4

示例3

输入：
15
输出：
4
解释：
15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示

• 1 <= N <= 10^9

题解

这是一道非常经典的数学题，挺基础的，不知道为什么这也能算困难难度的题目？

暴力法

遍历所有的连续数字区间 (i, j) ，然后求和看等不等于 N 。这种方法时间复杂度是 ，显然不可行。

暴力法优化

遍历所有的连续数字区间的左端点 i。然后假设区间长度为 n ，那么根据求和公式有 (2i+n-1)n/2=N ，然后只需要看这个方程的解是否是整数就行。时间复杂度可以降到 ，但还是太高了。

数学方法

根据上面的求和公式，对于起点 i 和长度 n ，求和得到 (2i+n-1)n/2=N 。我们可以先粗略推算一下 i 和 n 的范围，起点 i 的范围是 [1, N]毋庸置疑，而区间长度 n 的范围就可以考究一下了，一个出发点是：上面式子可以解出 i=(N-n(n-1)/2)/n ，而 i>=1 ，可以解出 (n+1)n<=2N ，所以 n 的范围其实只有根号 N 级别，可以直接遍历。另一个出发点是最小的 n 个数加起来就是 1 加到 n 等于 n(n+1)/2 ，这个要小于等于 N ，解出来也是 (n+1)n<=2N 。

所以我们只需要从 1 开始遍历 n ，直到 (n+1)n>2N 为止，然后判断 (N-n(n-1)/2)/n 是否是整数就行了（前面终止条件可以保证 i 一定大于 0 ）。

最终时间复杂度降到了 。

代码

数学方法（c++）

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 0;
        for (int n = 1; (n + 1) * n <= 2 * N; ++n) {
            if ((N - n * (n - 1) / 2) % n == 0) res++;
        }
        return res;
    }
};

数学方法（python）

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        res = 0
        for n in range(1, N+1):
            if n * (n + 1) > 2 * N:
                break
            if (N - n * (n - 1) // 2) % n == 0:
                res += 1
        return res

后记

这题还可以用质因数分解等方法进一步优化，但是没有必要。

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~