尧图网站建设 
LeetCode-Go 题解633. Sum of Square Numbers平方数之和——双指针夹逼判定与 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 633 题 Sum of Square Numbers平方数之和展开以仓库内 633 题官方题解文档 为骨架结合 Go 源码实现 与 单元测试 深入剖析其核心思路在区间[0, √c]上使用双指针README 中称为二分搜索判定整数c能否表示为两个平方数之和。读完本文你将掌握该题的双指针判定法、边界与溢出处理技巧以及如何在 LeetCode-Go 仓库中复用、测试这类实现。一、题目概览与判定目标英文原题Given a non-negative integerc, your task is to decide whether therere two integersaandbsuch that a² b² c.题目大意给定一个非负整数c判断是否存在两个整数a和b使得a² b² c。若存在则返回true否则返回false。题目中a、b限定为整数而非正整数但因为平方运算消除了符号影响(-a)² a²讨论时可以不失一般性地限定a, b ≥ 0同时0² 0也是一个合法的完全平方数因此a或b可以取0。官方示例示例 1Input: 5 Output: True Explanation: 1 * 1 2 * 2 5示例 2Input: 3 Output: False5 1² 2²显然成立而3无法拆成两个完全平方数之和0²3、1²2均不满足因此返回false。二、解题思路二分搜索 / 双指针夹逼题解文档给出的核心结论只有一句话但蕴含了完整的算法推导可以用二分搜索来解答这道题。判断题意依次计算low * low high * high和c是否相等。从[0, sqrt(n)]区间内进行二分若能找到则返回 true找不到就返回 false。将其展开为完整的推理链收缩搜索区间由a² b² c可知a² ≤ c且b² ≤ c即|a| ≤ √c、|b| ≤ √c。因此搜索空间只需覆盖[0, ⌊√c⌋]其余取值必不可能成为解。有序性带来夹逼性质区间内的数从小到大有序。若当前low² high² c说明当前和偏小必须增大其中一方而low是区间内可增的最小端点故low反之若和大于c说明当前和偏大必须减小一方而high是区间内可减的最大端点故high--。收敛性每一步要么low右移、要么high左移区间长度严格递减最多⌊√c⌋ 1步必然收敛若期间恰好low² high² c即命中解若指针交错low high则证明不存在这样的整数对。之所以题解文档称其为二分搜索指针收缩过程本质上是在有序搜索空间[0, ⌊√c⌋]上逐步剪枝而具体实现采用的则是**双向收缩双指针**形式——每次迭代丢弃区间的一端直到找到解或区间为空。两种表述描述的是同一套判定逻辑。三、源码实现逐行解析仓库中 633. Sum of Square Numbers.go 完整实现了上述思路全文如下package leetcode import math func judgeSquareSum(c int) bool { low, high : 0, int(math.Sqrt(float64(c))) for low high { if low*lowhigh*high c { low } else if low*lowhigh*high c { high-- } else { return true } } return false }逐行解读代码说明low, high : 0, int(math.Sqrt(float64(c)))初始化双指针low从最小平方根候选0出发high从最大候选⌊√c⌋出发。math.Sqrt接收float64需先做类型转换再截断为intfor low high循环不变量候选区间[low, high]尚未被排除指针尚未交错low*lowhigh*high c当前和小于c整体需要增大 →lowlow*lowhigh*high c当前和大于c整体需要减小 →high--else { return true }恰好相等找到一组整数解如a low, b highreturn false指针交错仍未命中说明c无法表示为两个平方数之和注意两个值得推敲的细节为什么从0而不是1开始题目允许整数取0因此c 10² 1²、c 40² 2²这类本身是完全平方数的输入也能被正确判定这也是测试用例中1 → true、4 → true的由来。平方和的计算位置low*low high*high每次循环重复计算两次比较分支中代码以可读性优先未做中间变量缓存优化属于风格取舍不影响正确性。四、复杂度分析时间复杂度O(√c)。low与high每次迭代至少移动一端搜索区间[0, ⌊√c⌋]最多被完整扫描一遍迭代次数上界为⌊√c⌋ 1math.Sqrt本身为常数时间。空间复杂度O(1)。仅使用low、high两个整型变量与若干临时值不依赖任何与输入规模相关的额外存储。对比暴力双循环枚举O(c)或优化后O(√c)的单循环枚举仍需额外哈希或判平方操作该双指针写法在时间、空间上均为当前思路下的最优形态与仓库 README 中runtime beats 100%的提交风格一致。五、测试用例验证与仓库运行方式测试文件结构Sum of Square Numbers_test.go 遵循仓库统一的表驱动测试模式定义question633含para633入参、ans633期望输出结构体在Test_Problem633中依次断言并在循环内打印输入输出便于人工核对。源码中实际覆盖的测试数据输入c期望输出数学依据1true0² 1²2true1² 1²3false无整数解4true0² 2²5true1² 2²对应官方示例 16false无整数解对应官方示例 2 的同族输入104976true0² 324²324² 104976即c本身为完全平方数用例覆盖了完全平方数1、4、104976、非完全平方数但有解2、5、无解3、6三类典型场景兼顾了0参与构造解与非平凡分解两种形态。如何运行在仓库根目录下可以针对单题运行go test -v -run Test_Problem633 ./leetcode/0633.Sum-of-Square-Numbers/也可以运行全量测试。仓库根目录的 gotest.sh 展示了官方的覆盖率收集方式一次性对全部leetcode/...包产出单一合法的覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...每个题目目录都遵循题号.题名/README.md 题号.go 题号_test.go的组织约定测试与题解一一对应这也是仓库实现高覆盖率的基础保障。六、边界情况与溢出讨论c 00² 0² 0low high 0时首次迭代即命中返回true。虽然当前测试集未显式包含该用例但算法天然覆盖。c为完全平方数high √c为整数low 0时直接命中如c 4、c 104976。浮点转整数的精度int(math.Sqrt(float64(c)))借助float64计算平方根。float64尾数 53 位对 LeetCode 约束范围0 ≤ c ≤ 2³¹ - 1内的完全平方数math.Sqrt结果足够精确即便high因浮点误差偏差 1循环中的大小比较也会立即纠正指针位置不会误判。整型溢出low*low high*high的理论最大值为2c。在 64 位平台下 Go 的int为 64 位对c ≤ 2³¹ - 1的输入完全安全若在 32 位平台或移植到其他语言时需要留意中间乘积的溢出风险可改用减法等价式或int64宽类型规避。七、延伸思考同一问题的其他解法双指针判定是本题最简洁的工程实现此外从数学与算法角度还有两条常见路线可作为面试或复习时的扩展讨论仓库当前仅实现双指针版本以下为思路介绍枚举 判平方对a从0到⌊√c⌋枚举检查c - a²是否是完全平方数开方后回乘验证。时间复杂度同为O(√c)空间O(1)但多一次math.Sqrt调用。费马两平方和定理数论判定正整数c能表示为两个整数平方和当且仅当其质因数分解中所有形如4k 3的质因子的指数均为偶数。该定理可给出O(√c)试除级别的确定性判定适合作为深入理解本题数学背景的延伸阅读工程上通常仍以双指针为准。八、总结Sum of Square Numbers 是有序搜索空间 双指针收缩这一经典范式的直接应用由a² b² c推导出搜索上界⌊√c⌋再利用平方和的单调性以O(√c)时间、O(1)空间完成判定。仓库内 题解文档、实现源码 与 表驱动测试 三位一体完整呈现了从思路到落地再到验证的闭环是阅读 LeetCode-Go 仓库时理解双指针类题目的一个高质量范例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：633. Sum of Square Numbers（平方数之和）——双指针夹逼判定与 Go 实现
LeetCode-Go 题解633. Sum of Square Numbers平方数之和——双指针夹逼判定与 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 633 题 Sum of Square Numbers平方数之和展开以仓库内 633 题官方题解文档 为骨架结合 Go 源码实现 与 单元测试 深入剖析其核心思路在区间[0, √c]上使用双指针README 中称为二分搜索判定整数c能否表示为两个平方数之和。读完本文你将掌握该题的双指针判定法、边界与溢出处理技巧以及如何在 LeetCode-Go 仓库中复用、测试这类实现。一、题目概览与判定目标英文原题Given a non-negative integerc, your task is to decide whether therere two integersaandbsuch that a² b² c.题目大意给定一个非负整数c判断是否存在两个整数a和b使得a² b² c。若存在则返回true否则返回false。题目中a、b限定为整数而非正整数但因为平方运算消除了符号影响(-a)² a²讨论时可以不失一般性地限定a, b ≥ 0同时0² 0也是一个合法的完全平方数因此a或b可以取0。官方示例示例 1Input: 5 Output: True Explanation: 1 * 1 2 * 2 5示例 2Input: 3 Output: False5 1² 2²显然成立而3无法拆成两个完全平方数之和0²3、1²2均不满足因此返回false。二、解题思路二分搜索 / 双指针夹逼题解文档给出的核心结论只有一句话但蕴含了完整的算法推导可以用二分搜索来解答这道题。判断题意依次计算low * low high * high和c是否相等。从[0, sqrt(n)]区间内进行二分若能找到则返回 true找不到就返回 false。将其展开为完整的推理链收缩搜索区间由a² b² c可知a² ≤ c且b² ≤ c即|a| ≤ √c、|b| ≤ √c。因此搜索空间只需覆盖[0, ⌊√c⌋]其余取值必不可能成为解。有序性带来夹逼性质区间内的数从小到大有序。若当前low² high² c说明当前和偏小必须增大其中一方而low是区间内可增的最小端点故low反之若和大于c说明当前和偏大必须减小一方而high是区间内可减的最大端点故high--。收敛性每一步要么low右移、要么high左移区间长度严格递减最多⌊√c⌋ 1步必然收敛若期间恰好low² high² c即命中解若指针交错low high则证明不存在这样的整数对。之所以题解文档称其为二分搜索指针收缩过程本质上是在有序搜索空间[0, ⌊√c⌋]上逐步剪枝而具体实现采用的则是**双向收缩双指针**形式——每次迭代丢弃区间的一端直到找到解或区间为空。两种表述描述的是同一套判定逻辑。三、源码实现逐行解析仓库中 633. Sum of Square Numbers.go 完整实现了上述思路全文如下package leetcode import math func judgeSquareSum(c int) bool { low, high : 0, int(math.Sqrt(float64(c))) for low high { if low*lowhigh*high c { low } else if low*lowhigh*high c { high-- } else { return true } } return false }逐行解读代码说明low, high : 0, int(math.Sqrt(float64(c)))初始化双指针low从最小平方根候选0出发high从最大候选⌊√c⌋出发。math.Sqrt接收float64需先做类型转换再截断为intfor low high循环不变量候选区间[low, high]尚未被排除指针尚未交错low*lowhigh*high c当前和小于c整体需要增大 →lowlow*lowhigh*high c当前和大于c整体需要减小 →high--else { return true }恰好相等找到一组整数解如a low, b highreturn false指针交错仍未命中说明c无法表示为两个平方数之和注意两个值得推敲的细节为什么从0而不是1开始题目允许整数取0因此c 10² 1²、c 40² 2²这类本身是完全平方数的输入也能被正确判定这也是测试用例中1 → true、4 → true的由来。平方和的计算位置low*low high*high每次循环重复计算两次比较分支中代码以可读性优先未做中间变量缓存优化属于风格取舍不影响正确性。四、复杂度分析时间复杂度O(√c)。low与high每次迭代至少移动一端搜索区间[0, ⌊√c⌋]最多被完整扫描一遍迭代次数上界为⌊√c⌋ 1math.Sqrt本身为常数时间。空间复杂度O(1)。仅使用low、high两个整型变量与若干临时值不依赖任何与输入规模相关的额外存储。对比暴力双循环枚举O(c)或优化后O(√c)的单循环枚举仍需额外哈希或判平方操作该双指针写法在时间、空间上均为当前思路下的最优形态与仓库 README 中runtime beats 100%的提交风格一致。五、测试用例验证与仓库运行方式测试文件结构Sum of Square Numbers_test.go 遵循仓库统一的表驱动测试模式定义question633含para633入参、ans633期望输出结构体在Test_Problem633中依次断言并在循环内打印输入输出便于人工核对。源码中实际覆盖的测试数据输入c期望输出数学依据1true0² 1²2true1² 1²3false无整数解4true0² 2²5true1² 2²对应官方示例 16false无整数解对应官方示例 2 的同族输入104976true0² 324²324² 104976即c本身为完全平方数用例覆盖了完全平方数1、4、104976、非完全平方数但有解2、5、无解3、6三类典型场景兼顾了0参与构造解与非平凡分解两种形态。如何运行在仓库根目录下可以针对单题运行go test -v -run Test_Problem633 ./leetcode/0633.Sum-of-Square-Numbers/也可以运行全量测试。仓库根目录的 gotest.sh 展示了官方的覆盖率收集方式一次性对全部leetcode/...包产出单一合法的覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...每个题目目录都遵循题号.题名/README.md 题号.go 题号_test.go的组织约定测试与题解一一对应这也是仓库实现高覆盖率的基础保障。六、边界情况与溢出讨论c 00² 0² 0low high 0时首次迭代即命中返回true。虽然当前测试集未显式包含该用例但算法天然覆盖。c为完全平方数high √c为整数low 0时直接命中如c 4、c 104976。浮点转整数的精度int(math.Sqrt(float64(c)))借助float64计算平方根。float64尾数 53 位对 LeetCode 约束范围0 ≤ c ≤ 2³¹ - 1内的完全平方数math.Sqrt结果足够精确即便high因浮点误差偏差 1循环中的大小比较也会立即纠正指针位置不会误判。整型溢出low*low high*high的理论最大值为2c。在 64 位平台下 Go 的int为 64 位对c ≤ 2³¹ - 1的输入完全安全若在 32 位平台或移植到其他语言时需要留意中间乘积的溢出风险可改用减法等价式或int64宽类型规避。七、延伸思考同一问题的其他解法双指针判定是本题最简洁的工程实现此外从数学与算法角度还有两条常见路线可作为面试或复习时的扩展讨论仓库当前仅实现双指针版本以下为思路介绍枚举 判平方对a从0到⌊√c⌋枚举检查c - a²是否是完全平方数开方后回乘验证。时间复杂度同为O(√c)空间O(1)但多一次math.Sqrt调用。费马两平方和定理数论判定正整数c能表示为两个整数平方和当且仅当其质因数分解中所有形如4k 3的质因子的指数均为偶数。该定理可给出O(√c)试除级别的确定性判定适合作为深入理解本题数学背景的延伸阅读工程上通常仍以双指针为准。八、总结Sum of Square Numbers 是有序搜索空间 双指针收缩这一经典范式的直接应用由a² b² c推导出搜索上界⌊√c⌋再利用平方和的单调性以O(√c)时间、O(1)空间完成判定。仓库内 题解文档、实现源码 与 表驱动测试 三位一体完整呈现了从思路到落地再到验证的闭环是阅读 LeetCode-Go 仓库时理解双指针类题目的一个高质量范例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考