LeetCode 633. 平方数之和

2024-10-16 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 633. 平方数之和

题意分析

给一个非负整数 c，问能不能找到两个非负整数 a 和 b 使得 $a^2 + b^2 = c$。

题面写的是「非负整数」，所以 a 或 b 取 0 是允许的。c = 1 的解是 $0^2 + 1^2$，c = 0 的解是 $0^2 + 0^2$，这两个边界最容易被「必须是正整数」的惯性思维排除掉。

约束信号有两处。第一，c 的上界是 $2^{31} - 1$，这个规模决定了 $O(c)$ 的枚举一定超时，而 $O(\sqrt{c})$（约四万六千次）绰绰有余。第二，也是更要命的一处：c 已经接近 int 的上限，两个平方数相加必然溢出 32 位有符号整数，所以中间量必须用 64 位存。

还有一个隐含的取值范围：因为平方都非负，$a^2 \le c$ 恒成立，所以 a 和 b 都落在 $[0, \lfloor \sqrt{c} \rfloor]$ 之间。这把无限的搜索空间压成了一个有界区间。

边界上要考虑：c = 0、c = 1、c 本身是完全平方数（此时一侧取 0）、以及 $a = b$ 的情形（例如 c = 2）。

解法：双指针

核心思路

暴力做法是双重循环枚举 a 和 b，各跑到 $\sqrt{c}$，复杂度 $O(c)$。c 取到 $2^{31}$ 量级时约二十一亿次运算，稳定超时。

稍好一点的做法是只枚举 a，然后判断 $c - a^2$ 是不是完全平方数，复杂度降到 $O(\sqrt{c})$。这条路是对的，但「判断完全平方数」如果用浮点开方再比小数部分，在大数上有精度隐患，要额外做取整回乘的校验。

更干净的做法来自一个观察：把 a 和 b 分别放在区间的两端，函数 $f(a, b) = a^2 + b^2$ 关于 a 单调递增、关于 b 也单调递增。这正是有序双指针成立的条件——当和偏小时，唯一能补救的方向是增大 a；当和偏大时，唯一能补救的方向是减小 b。每次调整都能安全地排除掉一整批候选，而不是只排除一个。

具体地说，令 left = 0、right = \lfloor \sqrt{c} \rfloor。若当前和小于 c，那么以当前 left 配任何不超过 right 的 b 都只会更小，left 这一列可以整体丢弃，left 右移；若当前和大于 c，那么以当前 right 配任何不小于 left 的 a 都只会更大，right 这一行可以整体丢弃，right 左移。

显式的不变量是：在每一步开始时，若存在满足 $a^2 + b^2 = c$ 且 $a \le b$ 的解，则一定有 $left \le a$ 且 $b \le right$，也就是解必然还在当前窗口 $[left, right]$ 里。指针交错说明窗口已空，可以断定无解。

循环条件必须写成 left <= right 而不是 left < right，因为 $a = b$ 是合法解（c = 2 就是 $1^2 + 1^2$），等号那一刻正是检验它的唯一机会。

解题步骤

把 left 初始化为 0。取 0 而不是 1，是因为题目允许其中一个数为零，c 是完全平方数时解就长这样。

把 right 初始化为 \lfloor \sqrt{c} \rfloor。这一步把搜索区间从 $[0, c]$ 直接压到 $[0, \sqrt{c}]$，是复杂度从 $O(c)$ 降到 $O(\sqrt{c})$ 的关键；若图省事写成 right = c，指针要白白左移二十亿次才进入有效区间。

循环条件用 left <= right，相等时仍要检验一次，对应 $a = b$ 的解。

每轮用 64 位整型计算 $left^2 + right^2$。必须是 64 位：c 接近 int 上限时两个平方和会超过 32 位范围。

和等于 c 就立刻返回 true。找到即返回，不要再动指针，否则会错过唯一解。

和小于 c 就 left++，因为增大较小的那一端是唯一能把和变大的动作。

和大于 c 就 right--，因为减小较大的那一端是唯一能把和变小的动作。

循环正常退出说明窗口已空，返回 false。

以 c = 5 走一遍：right 取 $\lfloor \sqrt{5} \rfloor = 2$，left = 0，窗口是 $[0, 2]$。

第一轮：$0^2 + 2^2 = 4$，小于 5。这说明 left = 0 配上区间里最大的 b = 2 都不够大，left = 0 整列被排除，left 变成 1。

第二轮：$1^2 + 2^2 = 1 + 4 = 5$，正好等于 c，返回 true，对应的解是 $a = 1$、$b = 2$。

再看无解用例 c = 3：right 取 $\lfloor \sqrt{3} \rfloor = 1$，窗口是 $[0, 1]$。第一轮 $0^2 + 1^2 = 1 < 3$，left 变成 1；第二轮 $1^2 + 1^2 = 2 < 3$，left 变成 2；此时 left = 2 大于 right = 1，循环退出，返回 false。注意第二轮正是 left == right 的那一刻，如果循环条件写成严格小于就会直接跳过它。

再看 c = 2：right 取 1，第一轮 $0 + 1 = 1 < 2$，left 变成 1；第二轮 left == right == 1，$1 + 1 = 2$ 命中，返回 true。这正是等号必须保留的证据。

代码实现

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

func judgeSquareSum(c int) bool {
    left := int64(0)
    right := int64(math.Sqrt(float64(c)))
    target := int64(c)

    for left <= right {
        sum := left*left + right*right
        if sum == target {
            return true
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(\sqrt{c})$，每轮循环必然让 left 右移一格或 right 左移一格，两者的总移动量不超过初始窗口宽度 $\lfloor \sqrt{c} \rfloor + 1$，因此循环次数受 $\sqrt{c}$ 约束；开方本身是常数时间。

空间复杂度：$O(1)$，只用了两个 64 位下标和一个临时和，没有开辟任何与 c 规模相关的数组或集合。

关键点总结

双指针能用的前提是目标函数在两个方向上都单调。这题 $a^2 + b^2$ 关于两端都是递增的，所以「偏小就动左端、偏大就动右端」这个决策是无歧义的。遇到新题时先验证单调性，再决定用不用双指针，比套模板可靠。

缩小搜索区间往往比优化循环体更值钱。把 right 的初值从 c 换成 $\sqrt{c}$，复杂度直接降了一个平方级，这一步的收益远大于任何常数优化。

数值题必须先算一遍中间量的上界再决定类型。这题 c 已经贴着 int 上限，两个平方相加必然溢出，用 64 位不是保险起见而是硬性要求。

left <= right 还是 left < right，取决于「两个下标能否指向同一个元素」。这题允许 $a = b$，等号必须留；如果题目要求两数不同，就该改成严格小于。写循环条件前先回题面确认一次。

面试视角：面试官常追问「有没有不用双指针的做法」。可以答费马平方和定理——c 能表示成两个平方数之和，当且仅当它的质因数分解中所有形如 $4k + 3$ 的质因子都出现偶数次；实现上是 $O(\sqrt{c})$ 试除。能顺带提一句「这个做法常数更大且容易写错，双指针在面试里更稳」，比单纯背定理更显判断力。

面试视角：另一个高频追问是「枚举 a 再判断 $c - a^2$ 是不是完全平方数行不行」。行，但要强调完全平方的判定得用「取整后回乘比对」而不是比较浮点小数部分，否则大数上会踩精度坑。主动指出这一点能展示你对数值边界的敏感度。

易错点总结

错误写法：用 32 位整型计算 left * left + right * right。用例 c 取到接近 $2^{31}$ 的量级（例如 c = 2147483600）→ right 初值约为 46340，left 稍微增大后平方和就超过 int 上限翻成负数，被误判为「和还不够大」，比较方向彻底失效，答案随机出错。

错误写法：循环条件写成 left < right。用例 c = 2 → right 是 1，left 增到 1 时循环立刻退出，$1^2 + 1^2 = 2$ 这个解从未被检验，返回 false，正确答案是 true。

错误写法：right 初始化成 c 而不是 $\lfloor \sqrt{c} \rfloor$。用例 c = 2147483647 → 指针要从 c 一路左移到 $\sqrt{c}$ 附近，约二十一亿次迭代，稳定超时。

错误写法：left 初始化成 1，认为两个数必须为正。用例 c = 4 → 唯一解是 $0^2 + 2^2$，left 从 1 起就再也碰不到它，最终返回 false，正确答案是 true。

错误写法：比较方向写反，和偏小时去左移右指针。用例 c = 5 → 第一轮 $0 + 4 = 4 < 5$ 却把 right 减到 1，之后和只会越来越小，指针交错后返回 false，正确答案是 true。

错误写法：认为 a 和 b 必须互不相同，命中时额外检查 left != right。用例 c = 2 → 唯一解 $1^2 + 1^2$ 被这条检查挡掉，返回 false，正确答案是 true。

错误写法：和等于 c 时不立刻返回，而是同时移动两个指针继续找。用例 c = 5 → 在 left = 1、right = 2 处已经命中，继续移动后变成 left = 2、right = 1 交错退出，返回 false，正确答案是 true。

错误写法：改用枚举 a 并靠 Math.sqrt(rest) % 1 == 0 判断 $c - a^2$ 是不是完全平方数。用例 c 很大时 rest 已经超出双精度尾数能精确表示的范围，开方结果的小数部分未必为零，本该成立的解被漏掉；稳妥写法是取整后回乘与 rest 比对。

相似题目

题目	难度	考察点
167. 两数之和 II - 输入有序数组	中等	同样的相向双指针，但单调性来自数组已排序而非函数性质
367. 有效的完全平方数	简单	只判一个数是否为平方，考察不用开方函数的二分或牛顿迭代
69. x 的平方根	简单	求整数平方根本身，正是本题 `right` 初值的手写实现