题目描述
给定一个正整数 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，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
