829.连续整数求和.md

829.连续整数求和

/*
 * @lc app=leetcode.cn id=829 lang=typescript
 *
 * [829] 连续整数求和
 */

// @lc code=start

// @lc code=end

解法 1: 数学

假设一个长度为 $i$ 最后一位为 $x$ 的连续数字之和为 $n$

$$ \begin{align*} n &= \frac{x(x+1)}{2}-\frac{(x-i)(x-(i-1))}{2} \\ &= \frac{2ix - i(i-1)}{2} \end{align*} $$

可以推导出 $x$ 和 $i$ 的关系

$$ x = \frac{2n+i(i-1)}{2i} $$

根据题意,需要保证 $x$ 为整数,并且 $x>=i$(当 $i>x$ 时,表示这个连续数字会出现负数,不满足题意)

可以通过枚举 $i$,判断 $x$ 满足上述条件,如果满足则表示找到一种有效的方案

通过 $x>=i$ 可以推导出 $i^2+i<=2*n$,所以时间复杂度为 $O(\sqrt{n})$ 级别,足够通过 $10^9$ 级别的数据

function consecutiveNumbersSum(n: number): number {
  let res = 0
  for (let i = 1; i ** 2 + i <= 2 * n; i++) {
    if ((2 * n + i * (i - 1)) % (2 * i) === 0) res++
  }
  return res
}

Case

test.each([
  { input: { n: 8504986 }, output: 16 },
  { input: { n: 5 }, output: 2 },
  { input: { n: 9 }, output: 3 },
  { input: { n: 15 }, output: 4 },
])('input: n = $input.n', ({ input: { n }, output }) => {
  expect(consecutiveNumbersSum(n)).toEqual(output)
})