LeetCode 279. Perfect Squares 完全平方数四平方定理在 LeetCode-Go 中的数论解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 leetcode/0279.Perfect-Squares/README.md 为骨架讲解 LeetCode 第 279 题「完全平方数」Perfect Squares在 LeetCode-Go 仓库中的实现方案。该题要求将正整数n分解为最少数量的完全平方数之和仓库给出的解法没有采用常规的 DP动态规划而是基于拉格朗日四平方定理与三平方推论将答案压缩到1 / 2 / 3 / 4四选一时间复杂度仅为 O(√n)。读完本文你将掌握题目本身的建模方式、两条数论定理如何直接给出答案上界与判定条件、仓库源码中isPerfectSquare与checkAnswer4两个辅助函数的实现原理以及如何用仓库自带的表驱动测试验证结果。一、题目回顾最少完全平方数之和题目描述给定一个整数n返回和为n的完全平方数的最少数量。完全平方数是指一个整数等于另一个整数的平方即它是某个整数自乘的积。例如1 1²、4 2²、9 3²、16 4²都是完全平方数而3、11不是。示例 1Input: n 12 Output: 3 Explanation: 12 4 4 4.示例 2Input: n 13 Output: 2 Explanation: 13 4 9.约束条件1 n 10⁴。题目的中文大意是给定正整数n找到若干个完全平方数比如 1、4、9、16 ……使得它们的和等于n并让组成和的完全平方数个数最少返回这个最少数量。二、核心思路用数论定理替代动态规划面对求最少个数这类最值问题第一直觉往往是 DP令dp[i]表示和为i所需的最少完全平方数个数转移方程为dp[i] min(dp[i], dp[i - j*j] 1)复杂度为 O(n·√n)。但本仓库选择了另一条更巧妙的路径——先通过数论定理锁定答案的上界与候选值再逐一验证。README 的解题思路部分给出了两条关键定理拉格朗日四平方定理Lagranges Four-Square Theorem每个自然数都可以表示为至多四个整数的平方之和。这直接给出了本题答案的上界——任何n的答案都不超过 4。三平方推论Legendres Three-Square Theorem当且仅当n ≠ 4^k × (8m 7)时n可以表示为至多三个正整数的平方和反过来当n 4^k × (8m 7)时n只能表示为四个正整数的平方和此时答案直接就是 4。于是答案被限制在{1, 2, 3, 4}之中问题退化为四个布尔判断完全不需要遍历所有组合。三、判定顺序推导为什么是 1 → 4 → 2 → 3在n ≠ 4^k × (8m 7)的前提下答案只可能是 1、2、3 中的一个。仓库代码采用的判定顺序是先判答案是否为 1若n本身是完全平方数即存在整数a使n a²答案为 1。再判答案是否为 4若n 4^k × (8m 7)根据三平方推论n不能被表示为三个以内平方数之和结合四平方定理的上界答案只能为 4。再判答案是否为 2若存在整数a, b使n a² b²答案为 2。实现上枚举1 ≤ a ≤ √n对每个a检查n - a²是否为完全平方数。兜底返回 31 和 2 都被排除、4 的形态也不满足时剩余答案只能是 3。这个顺序保证了从最小答案开始逐个验证的贪心逻辑一旦某个更小的数量被证明可行立即返回无需继续判断。四、源码逐行解析完整实现位于 279. Perfect Squares.go与 README 中的代码完全一致package leetcode import math func numSquares(n int) int { if isPerfectSquare(n) { return 1 } if checkAnswer4(n) { return 4 } for i : 1; i*i n; i { j : n - i*i if isPerfectSquare(j) { return 2 } } return 3 } // 判断是否为完全平方数 func isPerfectSquare(n int) bool { sq : int(math.Floor(math.Sqrt(float64(n)))) return sq*sq n } // 判断是否能表示为 4^k*(8m7) func checkAnswer4(x int) bool { for x%4 0 { x / 4 } return x%8 7 }4.1 主函数numSquares的四个分支分支 1isPerfectSquare(n)为真时直接返回 1。这是最优情形例如n 1、n 4、n 9。分支 2checkAnswer4(n)为真时返回 4。对应n 4^k × (8m 7)的形态例如n 7、n 15、n 28。这里的返回不依赖任何枚举是纯数论结论的直接落地。分支 3两层判定合二为一——外层枚举i从 1 到√n循环条件i*i n保证i不超过√n内层令j n - i*i并检查j是否为完全平方数。这等价于寻找整数解n i² j²。一旦命中立即返回 2例如n 13 4 9、n 2 1 1。兜底三个条件全部不满足时返回 3。此时n既不是完全平方数也不满足四平方形态且无法写成两个平方数之和由三平方推论可知答案必为 3例如n 12 4 4 4。4.2 辅助函数isPerfectSquare浮点开方 平方回验func isPerfectSquare(n int) bool { sq : int(math.Floor(math.Sqrt(float64(n)))) return sq*sq n }实现要点先通过math.Sqrt对float64(n)开方用math.Floor向下取整得到整数近似根sq再验证sq*sq n。由于n ≤ 10⁴开方结果的精度损失完全可以忽略回验机制保证了浮点误差不会造成误判。这个函数同时服务于主函数的分支 1 与分支 3是整套判定的基石。4.3 辅助函数checkAnswer4剥离因子 4 后判断模 8func checkAnswer4(x int) bool { for x%4 0 { x / 4 } return x%8 7 }这是三平方推论的直接编码。由于4^k × (8m 7)中的因子4^k会被8m 7的奇偶性掩盖实现上先用循环把因子 4 全部剥离x不断除以 4 直到不能被 4 整除再判断剩余部分对 8 取模是否等于 7。若为真说明n只能表示为四个完全平方数之和返回 4。五、复杂度分析时间复杂度O(√n)。三个分支中分支 3 的枚举上界是√n其余两个辅助函数均为常数级操作因此总体为 O(√n)远优于 DP 方案的 O(n·√n)。空间复杂度O(1)。整个过程只使用了若干整数变量没有任何额外数据结构。这一点与 DP 形成鲜明对比DP 需要 O(n) 的数组记录中间状态而数论解法把空间压到了常数级。六、测试用例与运行验证仓库为本题提供了表驱动测试位于 279. Perfect Squares_test.go。测试结构遵循 LeetCode-Go 的统一约定para279封装输入参数nans279封装期望答案question279将二者组合type question279 struct { para279 ans279 } type para279 struct { n int } type ans279 struct { one int }测试数据覆盖了四种返回值恰好印证了前文的四个分支输入 n期望输出对应答案分支依据1111 1²完全平方数分支 17447 4⁰ × (8×0 7)满足四平方形态分支 2132213 2² 3²分支 31233三种条件均不满足兜底返回 312 4 4 4在仓库根目录运行以下命令即可执行本题含全部其他题目的测试go test ./leetcode/0279.Perfect-Squares/ -v -run Test_Problem279测试运行时会打印每个用例的输入与输出例如【input】:13 【output】:2 【input】:12 【output】:3 【input】:1 【output】:1 【input】:7 【output】:4七、延伸讨论何时该用数论解法本题的 DP 解法dp[i] min(dp[i], dp[i - j*j] 1)通用性更强能覆盖恰好使用 k 个平方数之类的变体而数论解法依赖拉格朗日四平方定理与三平方推论的强结论只有当题目明确要求最少数量且答案上界为 4 时才能生效。在本仓库的实现中n ≤ 10⁴的约束下 O(√n) 的复杂度几乎瞬时完成同时 O(1) 的空间开销让它成为一道展示数学建模优于暴力枚举的典型案例。值得留意的是isPerfectSquare中浮点开方 平方回验的手法在仓库内是通用技巧可用于判断完全平方数的其他场景checkAnswer4中剥离 4 的因子再取模则是将数论条件翻译成代码的简洁范本。读者可以把这两个辅助函数的思路迁移到其他涉及完全平方数判定的题目中。参考与深入阅读题目文档leetcode/0279.Perfect-Squares/README.md核心实现279. Perfect Squares.go表驱动测试279. Perfect Squares_test.go项目根 READMEREADME.md内含仓库整体结构与测试约定gotest.sh可一键跑完全部测试【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考