当前位置：网站首页>leetcode-829. 连续整数求和（数论）

leetcode-829. 连续整数求和（数论）

2022-07-31 05:10:00 【lin钟一】

在这里插入图片描述
题目链接：https://leetcode.cn/problems/consecutive-numbers-sum/

思路

方法：数论

直接想法
这题求连续正整数，刚好满足等差数列，可以用等差数列求和公式 n = (i + (i + k)) * (k + 1) / 2 其中i是连续正整数的首项，k是尾项和首项的差值
题目给定范围是10⁹
方法一：用枚举i和k 需要O(n²) 肯定超时
方法二：枚举i 和二分k 需要O(n * logn) 也肯定超时
只能控制时间复杂度在O(n)的时间
所以我们需要用更好的方法求出答案，我们推导等差数列求和公式可以发现

在这里插入图片描述

2n = a * b，我们只需要枚举 2n的因子，再通过2i = a - （b - 1）是否满足 2i 为偶数且大于零即可找出答案，但是这样还不够，2n最差时间复杂度需要2 * 10 ⁹ 依旧会超时。
我们可以只枚举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
}