class Solution {
public:
int consecutiveNumbersSum(int n) {
}
};
829. 连续整数求和
给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。
示例 1:
输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。
示例 2:
输入: n = 9 输出: 3 解释: 9 = 4 + 5 = 2 + 3 + 4
示例 3:
输入: n = 15 输出: 4 解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
提示:
1 <= n <= 109原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 38.3 MB, 提交时间: 2022-11-28 13:21:37
class Solution {
public int consecutiveNumbersSum(int n) {
int ans = 0;
int bound = 2 * n;
for (int k = 1; k * (k + 1) <= bound; k++) {
if (isKConsecutive(n, k)) {
ans++;
}
}
return ans;
}
public boolean isKConsecutive(int n, int k) {
if (k % 2 == 1) {
return n % k == 0;
} else {
return n % k != 0 && 2 * n % k == 0;
}
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 41.1 MB, 提交时间: 2022-11-28 13:21:20
/**
* @param {number} n
* @return {number}
*/
var consecutiveNumbersSum = function(n) {
let ans = 0;
const bound = 2 * n;
for (let k = 1; k * (k + 1) <= bound; k++) {
if (isKConsecutive(n, k)) {
ans++;
}
}
return ans;
}
const isKConsecutive = (n, k) => {
if (k % 2 === 1) {
return n % k === 0;
} else {
return n % k !== 0 && 2 * n % k === 0;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-28 13:21:05
func isKConsecutive(n, k int) bool {
if k%2 == 1 {
return n%k == 0
}
return n%k != 0 && 2*n%k == 0
}
func consecutiveNumbersSum(n int) (ans int) {
for k := 1; k*(k+1) <= n*2; k++ {
if isKConsecutive(n, k) {
ans++
}
}
return
}
python3 解法, 执行用时: 196 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-28 13:20:37
'''
k个连续整数 k * (k + 1) = n * 2
最小的那个 x = n/k - (k-1)/2
'''
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
def isKConsecutive(n: int, k: int) -> bool:
if k % 2:
return n % k == 0
return n % k and 2 * n % k == 0
ans = 0
k = 1
while k * (k + 1) <= n * 2:
if isKConsecutive(n, k):
ans += 1
k += 1
return ans