2020-02-14 04:03:18 +00:00
|
|
|
|
# [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/)
|
|
|
|
|
|
|
|
|
|
|
|
# 思路
|
|
|
|
|
|
|
|
|
|
|
|
给定正整数N，问N能写成多少种连续正整数之和，比如9可以写成 4+5，或者2+3+4。
|
|
|
|
|
|
|
|
|
|
|
|
我们假设把N拆分成k个连续的数之和，并设最小的那个数是m，则我们有：
|
|
|
|
|
|
|
|
|
|
|
|
|k| 1 | 2 | 3 | 4 | ... | K |
|
2020-02-14 04:19:52 +00:00
|
|
|
|
|---|:-:|:-:|:-:|:-:|:-:|:-:|
|
2020-02-14 04:03:18 +00:00
|
|
|
|
|连续序列|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++
|
|
|
|
|
|
``` 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;
|
|
|
|
|
|
}
|
|
|
|
|
|
};
|
|
|
|
|
|
```
|
