小鲸鱼的梦境
0%

『LeetCode』829 连续整数求和

发表于 分类于 Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目

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 <= 10^{9}\)​​​​​​​

题解

【连续整数求和】简单枚举

枚举

众所周知，以正整数 \(a\) 为起点的连续 \(k\) 个数字之和可以使用等差数列求和公式计算：

\[ \begin{aligned} n &= \dfrac{(a + (a + k - 1)) \times k}{2} \\ &= \dfrac{(2a + k - 1) \times k}{2} \end{aligned} \]

从题目中得知，我们已知和为 \(n\), 那么就要求上述方程的正整数解，但有两个未知数 \(a, k\)，一种简单的思路是：枚举其中一个数，那么另外一个数字就能计算出来了，我们只需验证得到的解是否合法即可，这里的合法是指解出的 \(a, k\) 应该是正整数。

相比之下，枚举连续数字的个数 \(k\) 比枚举起点 \(a\) 要容易一些，将公式变形，即

\[ a = \dfrac{\cfrac{2n}{k} + 1 - k}{2} \]

那么还剩下一个问题是，枚举到什么时候终止呢？换而言之，\(k\) 最大取值是多少？

不难发现，在和一定的情况下，以 \(1\) 为起点得到的数列是最长的，即 \(a = 1\) 代入时得到的 \(k\) 最大，所以当我们计算到 \(a < 1\) 即可终止。

1
2
3
4
5
6
7
8
9
10
11
# Code language: Python
class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        cnt = 1
        for k in range(2, n):
            a = (2 * n // k + 1 - k) // 2
            if a < 1:
                break
            elif n == (2 * a + k - 1) * k // 2:
                cnt += 1
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Code language: Java
class Solution {
    public int consecutiveNumbersSum(int _n) {
        // (2 * a + k - 1) * k / 2 = n
        // (2 * n / k + 1 - k) / 2 = a
        int cnt = 1;
        for (long k = 2, n = _n; ; ++k) {
            long a = (2 * n / k + 1 - k) / 2;
            if (a < 1) break;
            long s = (2 * a + k - 1) * k / 2;
            if (s == n) ++cnt;
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Code language: C++
class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int cnt = 1;
        for (long k = 2; ; ++k) {
            long a = (2 * n / k + 1 - k) / 2;
            if (a < 1) break;
            long s = (2 * a + k - 1) * k / 2;
            if (s == n) ++cnt;
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
// Code language: C
int consecutiveNumbersSum(int n){
    int cnt = 1;
    for (long k = 2; ; ++k) {
        long a = (2 * n / k + 1 - k) / 2;
        if (a < 1) break;
        long s = (2 * a + k - 1) * k / 2;
        if (s == n) ++cnt;
    }
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// Code language: C#
public class Solution {
    public int ConsecutiveNumbersSum(int n) {
        int cnt = 1;
        for (long k = 2; ; ++k) {
            long a = (2 * n / k + 1 - k) / 2;
            if (a < 1) break;
            long s = (2 * a + k - 1) * k / 2;
            if (s == n) ++cnt;
        }
        return cnt;
    }
}
  • 时间复杂度：\(O(\sqrt{n})\), 易得 \(k^2 +(2a - 1)k = 2n \Rightarrow k^2 \leq 2n \Rightarrow k \leq \sqrt{2n}\)
  • 空间复杂度: \(O(1)\)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~