LeetCode 补拙笔记

0. 前言

• 日期：2026.08.31
• 题目：3658. 奇数和与偶数和的最大公约数
• 难度：简单
• 标签：数学、最大公约数、等差数列求和

1. 题目理解

问题描述 给定整数n，计算两个值的最大公约数： sumOdd：最小的n个正奇数总和； sumEven：最小的n个正偶数总和； 返回sumOdd和sumEven的GCD。

示例

输入：n = 4 输出：4 解释： sumOdd = 1+3+5+7 = 16 sumEven = 2+4+6+8 = 20 gcd(16,20)=4

2. 解题思路

核心观察

1. 前n个奇数：等差数列，首项1，公差2，求和公式 $sumOdd=n^2$
2. 前n个偶数：等差数列，首项2，公差2，求和公式 $sumEven=n(n+1)$
3. 求 $gcd(n^2,n(n+1))$；n与n+1互质，所以 $gcd(n^2,n(n+1))=n\ast gcd(n,n+1)=n$。
4. 数学结论：答案直接等于n，不需要循环计算gcd；原版使用欧几里得辗转相除法实现GCD。

算法步骤

原版：

1. 利用公式算出sumOdd=$n^2$，sumEven=$n(n+1)$
2. 实现辗转相除法求两个数最大公约数，返回结果。

数学优化：

1. 直接返回n，消除gcd函数与循环，去掉if分支。

3. 代码实现

package lc3600_lc3699.lc3658;

class Solution {
    public int gcdOfOddEvenSums(int n) {
        if(n==1){return 1;}
        int a = 0;
        int b = 0;
        a = n * n;
        b = a + n;

        return gcd(a, b);
    }

    private int gcd(int a, int b) {
        int res = 0;
        while (true) {
            res = b % a;
            if (res == 0) {
                return b;
            } else {
                a = b;
                b = res;
            }
        }
    }
}

4. 代码优化说明

class Solution {
    public int gcdOfOddEvenSums(int n) {
        //数学推导：gcd(n², n(n+1)) = n，n和n+1互质
        return n;
    }
}

5. 复杂度分析

• 原版代码 时间复杂度：$O(log(min(a,b)))$，辗转相除法循环；存在if分支判断 空间复杂度：$O(1)$，仅使用常数临时变量

• 数学优化版 时间复杂度：$O(1)$，直接返回结果，无循环、无条件分支 空间复杂度：$O(1)$，无额外变量

6. 总结

• 核心：利用等差数列求和公式得到两个和的表达式，利用互质性质推导数学结论；
• 优化亮点：通过数学推导，直接返回n，彻底删除gcd函数、循环和if判断；
• 关键点：相邻两个整数n与n+1一定互质，最大公约数为1，这是本题的关键数学性质。