• 2024-03-14 leetcode写题记录
  • 829. 连续整数求和
    • 题目链接
    • 题意
    • 解法

2024-03-14 leetcode写题记录

829. 连续整数求和

题目链接

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

解法

连续正整数之和，可以写为\(n = \frac{r(r+1)}{2} - \frac{l(l+1)}{2}\)，两边乘\(2\)，可得

\( \begin{align} 2n &= r(r+1) - l(l+1) \nonumber \\ &= r^2 + r - l^2 - l \nonumber \\ &= (r + l + 1)(r - l) \nonumber \end{align} \)

由于以下性质：

（1）\(r+l+1\)和\(r-l\)的乘积为\(2n\)；

（2）\(r+l+1\)与\(r-l\)奇偶性不同；

（3）\(r+l+1\)严格大于\(r-l\)；

（4）任何两个奇偶性不同的正整数\(r+l+1\)与\(r-l\)，都一定有自然数\(r\)和\(l\)与其一一对应（证明很简单，列下方程组就行）。

所以我们只需要遍历\([1,\sqrt{2n})\)，求出能整除\(2n\)，且\(2n / i\)和\(i\)奇偶性不同的\(i\)的个数就行。

时间复杂度显然为\(O(\sqrt{n})\)。

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int cnt = 0;
        for (int i = 1; 1ll * i * i < 2 * n; ++i)
            if (2 * n % i == 0 && (i ^ (2 * n / i)) & 1)
                cnt++;
        return cnt;
    }
};