题目链接：https://leetcode.cn/problems/consecutive-numbers-sum/
思路
方法：数论
直接想法
这题求连续正整数，刚好满足等差数列，可以用等差数列求和公式 n = (i + (i + k)) * (k + 1) / 2 其中i是连续正整数的首项，k是尾项和首项的差值
题目给定范围是109
方法一：用枚举i和k 需要O(n2) 肯定超时
方法二：枚举i 和 二分k 需要O(n * logn) 也肯定超时
只能控制时间复杂度在O(n)的时间
所以我们需要用更好的方法求出答案，我们推导等差数列求和公式可以发现
2n = a * b，我们只需要枚举 2n的因子，再通过2i = a - （b - 1）是否满足 2i 为偶数且大于零即可找出答案，但是这样还不够，2n最差时间复杂度需要2 * 10 9 依旧会超时。
我们可以只枚举a， b用n/a代替判断，只需要循环枚举2n的平方根
代码示例
func check(a, b int) bool{ i2 := a - (b - 1) if i2 & 1 == 1{ return false } if i2 <= 0{ return false } return true } func consecutiveNumbersSum(n int) (ans int) { n *= 2 sq := int(math.Sqrt(float64(n))) for i := 1; i <= sq; i++{ if n % i == 0{ if check(i, n / i){ ans++ } if i != n / i{ if check(n / i, i){ ans++ } } } } return }
复杂度分析
- 时间复杂度：O(sqrt(2 * n)) 我们只需要循环枚举根号2n，找出他的所有因子即可
- 空间复杂度：O(1) 不需要额外申请空间
