困难

问题描述

给定一个正整数 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

数学

假设存在某个连续的序列和为 $n$，设首项为 $a$，项数为 $k$，根据 等差数列求和公式可得

$$\frac {(a + a + k - 1) \times k}{2} = n$$

变形可得

$$(2a + k - 1) \times k = 2n \Leftrightarrow 2a = \frac {2n}{k} - k + 1$$

因为首项跟项数都大于 $0$，因此有

$$2a = \frac {2n}{k} - k + 1 \geq 2$$

进一步可得

$$\frac {2n}{k} \geq k + 1 \Rightarrow \frac {2n}{k} \gt k \Leftrightarrow 2n \gt k^2$$

即项数 $k$ 的取值范围为 $[1, \sqrt {2n})$ ，因为已经推导得出 $2a = \frac {2n}{k} - k + 1$，枚举此范围内的全部值 $k$，即可得到 $2a$ 的全部可能的值，由于首项必须是正整数，因此满足 $\frac {2n}{k} - k + 1 \; \text {mod} \; 2 = 0$ 即是合法的序列 $[a, \dots , a + k - 1]$，统计合法序列个数即可。

/**
 * @param {number} n
 * @return {number}
 */
var consecutiveNumbersSum = function (n) {
  let ans = 0
  let m = n * 2
  for (let k = 1; k * k < m; k++) {
    // 不能整除直接跳过
    if (m % k != 0) continue
    if ((m / k - k + 1) % 2 === 0) ans++
  }
  return ans
}

• 时间复杂度：$O(\sqrt {2n})$
• 空间复杂度：$O(1)$