Java&C++题解与拓展——leetcode829.连续整数求和【么的新知识】

发布时间:2023-08-07 19:30

每日一题做题记录,参考官方和三叶的题解

目录

  • 题目要求
  • 思路:数论
    • Java
    • C++
    • Rust
  • 总结

题目要求

\"Java&C++题解与拓展——leetcode829.连续整数求和【么的新知识】_第1张图片\"

思路:数论

  • 连续段之和得到 n n n,那么可以找到一个长度为 k k k的连续段,其首项为 a a a,三者之间满足一些关系以构成答案。
    • 具体来说,由等差数列求和公式得 ( a + a + k − 1 ) × k 2 = n \\frac{(a+a+k-1)\\times k}{2}=n 2(a+a+k1)×k=n
    • 变换可得, 2 a = 2 n k − k + 1 ≥ 2 2a=\\frac{2n}{k}-k+1\\ge 2 2a=k2nk+12
    • 也就是说, 2 n k ≥ k + 1 ⇔ 2 n k > k \\frac{2n}{k}\\ge k+1\\Leftrightarrow \\frac{2n}{k}\\gt k k2nk+1k2n>k
    • k k k必然是 2 n 2n 2n的约数,且是较小的那一方,所以枚举 k k k并判断等差数列和即可。

Java

class Solution {
    public int consecutiveNumbersSum(int n) {
        int res = 0;
        n *= 2;
        for(int k = 1; k * k < n; k++) {
            if(n % k != 0)
                continue;
            if((n / k - (k - 1)) % 2 == 0)
                res++;
        }
        return res;
    }
}
  • 时间复杂度: O ( 2 n ) O(\\sqrt{2n}) O(2n )
  • 空间复杂度: O ( 1 ) O(1) O(1)

C++

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int res = 0;
        n *= 2;
        for(int k = 1; k * k < n; k++) {
            if(n % k != 0)
                continue;
            if((n / k - (k - 1)) % 2 == 0)
                res++;
        }
        return res;
    }
};
  • 时间复杂度: O ( 2 n ) O(\\sqrt{2n}) O(2n )
  • 空间复杂度: O ( 1 ) O(1) O(1)

Rust

  • 换了一个复杂度更低的高赞方式;
  • 1个数时,必然有一个数可构成N
  • 2个数若要构成N,第2个数与第1个数差为1,N减掉这个1能整除2则能由商与商+1构成N
  • 3个数若要构成N,第2个数与第1个数差为1,第3个数与第1个数的差为2,N减掉1再减掉2能整除3则能由商、商+1与商+2构成N
  • 以此类推,当商即第1个数小于等于0时结束
impl Solution {
    pub fn consecutive_numbers_sum(n: i32) -> i32 {
        let mut res = 0;
        let mut k = 1;
        let mut n = n;
        while n > 0 {
            n -= k;
            if n % k == 0 {
                res += 1;
            }
            k += 1;
        }
        res
    }
}
  • 时间复杂度: O ( n ) O(\\sqrt{n}) O(n )
  • 空间复杂度: O ( 1 ) O(1) O(1)

总结

数学理论分析更重要的题。


欢迎指正与讨论!

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号