目录
题目要求
思路：数论
- 连续段之和得到
n
n
n，那么可以找到一个长度为
k
k
k的连续段，其首项为
a
a
a，三者之间满足一些关系以构成答案。
- 具体来说，由等差数列求和公式得
(
a
+
a
+
k
−
1
)
×
k
2
=
n
frac{(a+a+k-1)times k}{2}=n
2(a+a+k−1)×k=n
- 变换可得，
2
a
=
2
n
k
−
k
+
1
≥
2
2a=frac{2n}{k}-k+1ge 2
2a=k2n−k+1≥2
- 也就是说，
2
n
k
≥
k
+
1
⇔
2
n
k
>
k
frac{2n}{k}ge k+1Leftrightarrow frac{2n}{k}gt k
k2n≥k+1⇔k2n>k
- 即
k
k
k必然是
2
n
2n
2n的约数，且是较小的那一方，所以枚举
k
k
k并判断等差数列和即可。
Java
class Solution {
public int consecutiveNumbersSum(int n) {
int res = 0;
n *= 2;
for(int k = 1; k * k < n; k++) {
if(n % k != 0)
continue;
if((n / k - (k - 1)) % 2 == 0)
res++;
}
return res;
}
}
- 时间复杂度：
O
(
2
n
)
O(sqrt{2n})
O(2n
)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
C++
class Solution {
public:
int consecutiveNumbersSum(int n) {
int res = 0;
n *= 2;
for(int k = 1; k * k < n; k++) {
if(n % k != 0)
continue;
if((n / k - (k - 1)) % 2 == 0)
res++;
}
return res;
}
};
- 时间复杂度：
O
(
2
n
)
O(sqrt{2n})
O(2n
)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
Rust
- 1个数时，必然有一个数可构成N
- 2个数若要构成N，第2个数与第1个数差为1，N减掉这个1能整除2则能由商与商+1构成N
- 3个数若要构成N，第2个数与第1个数差为1，第3个数与第1个数的差为2，N减掉1再减掉2能整除3则能由商、商+1与商+2构成N
- 以此类推，当商即第1个数小于等于0时结束
impl Solution {
pub fn consecutive_numbers_sum(n: i32) -> i32 {
let mut res = 0;
let mut k = 1;
let mut n = n;
while n > 0 {
n -= k;
if n % k == 0 {
res += 1;
}
k += 1;
}
res
}
}
- 时间复杂度：
O
(
n
)
O(sqrt{n})
O(n
)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
总结
数学理论分析更重要的题。
