Hard

题目描述

给定一个整数 n，返回用连续的正整数表示 n 的方案数。

示例 1：

输入：n = 5
输出：2
解释：5 = 2 + 3

示例 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 <= 10^9

解题思路

这是一道数学问题，关键是理解连续正整数和的数学性质。

假设我们用 k 个连续正整数表示 n，起始数为 start，那么有：

n = start + (start + 1) + ... + (start + k - 1)
n = k * start + k * (k - 1) / 2

整理得到：start = (n - k * (k - 1) / 2) / k

为了使 start 为正整数，需要满足：

  1. n - k * (k - 1) / 2 > 0，即 n > k * (k - 1) / 2
  2. (n - k * (k - 1) / 2) % k == 0

从数学角度分析，第二个条件等价于：

  • 当 k 为奇数时，n 必须能被 k 整除
  • 当 k 为偶数时，n 除以 k 的余数必须是 k/2

我们可以枚举所有可能的 k 值，从 1 开始直到 k * (k - 1) / 2 >= n。对于每个 k，检查是否满足上述条件。

时间复杂度优化：由于 k * (k - 1) / 2 < n，所以 k 的最大值约为 √(2n)，因此算法效率很高。

代码实现

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int count = 0;
        for (int k = 1; k * (k - 1) / 2 < n; k++) {
            if (k % 2 == 1) {
                if (n % k == 0) count++;
            } else {
                if (n % k == k / 2) count++;
            }
        }
        return count;
    }
};

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        count = 0
        k = 1
        while k * (k - 1) // 2 < n:
            if k % 2 == 1:
                if n % k == 0:
                    count += 1
            else:
                if n % k == k // 2:
                    count += 1
            k += 1
        return count

public class Solution {
    public int ConsecutiveNumbersSum(int n) {
        int count = 0;
        for (int k = 1; k * (k - 1) / 2 < n; k++) {
            if (k % 2 == 1) {
                if (n % k == 0) count++;
            } else {
                if (n % k == k / 2) count++;
            }
        }
        return count;
    }
}

var consecutiveNumbersSum = function(n) {
    let count = 0;
    
    for (let k = 1; k * (k - 1) / 2 < n; k++) {
        if ((n - k * (k - 1) / 2) % k === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(√n)
空间复杂度O(1)