829. Consecutive Numbers Sum.md

829. Consecutive Numbers Sum

思路

给定正整数N，问N能写成多少种连续正整数之和，比如9可以写成 4+5，或者2+3+4。

我们假设把N拆分成k个连续的数之和，并设最小的那个数是m，则我们有：

k	1	2	3	4	...	K
连续序列	m	m,m+1	m,m+1,m+2	m,m+1,m+2,m+3	...	m,m+1,m+K-1
满足关系	N=m	N = 2m+1	N = 3m+3	N = 4m+6	...	N = Km + f(k)

其中 f(k) = 1 + 2 +...+ k-1。

有了这个规律我们就知道了如果 (N - f(k)) % k == 0则说明可以拆成k个连续的数，那我们就可以从 k=1 不断增大k直到不满足N <= f(k)即可。

由于 f(k) = 1 + 2 +...+ k-1 = (k*k-1)/2。所以k最大为 sqrt(2N) 向下取整。所以时间复杂度为O(sqrt(N))。

C++

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 0, k = 1, fk = 0;
        while(N > fk){
            if((N - fk) % k == 0) res++;
            fk += (k++);
        }
        return res;
    }
};