题目描述
这是 LeetCode 上的 633. 平方数之和 ，难度为 中等。
Tag : 「数学」、「双指针」
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2a^2a2 + b2b^2b2 = c 。
示例 1：
输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5 复制代码
示例 2：
输入：c = 3 输出：false 复制代码
示例 3：
输入：c = 4 输出：true 复制代码
示例 4：
输入：c = 2 输出：true 复制代码
示例 5：
输入：c = 1 输出：true 复制代码
提示：
- 0 <= c <= 2312^{31}231 - 1
基本分析
根据等式 a2+b2=ca^2 + b^2 = ca2+b2=c，可得知 a 和 b 的范围均为 [0,c][0,\sqrt{c}][0,c]。
基于此我们会有以下几种做法。
枚举
我们可以枚举 a ，边枚举边检查是否存在 b 使得等式成立。
这样做的复杂度为 O(c)O(\sqrt{c})O(c)。
代码：
class Solution { public boolean judgeSquareSum(int c) { int max = (int)Math.sqrt(c); for (int a = 0; a <= max; a++) { int b = (int)Math.sqrt(c - a * a); if (a * a + b * b == c) return true; } return false; } } 复制代码
- 时间复杂度：O(c)O(\sqrt{c})O(c)
- 空间复杂度：O(1)O(1)O(1)
双指针
由于 a 和 b 的范围均为 [0,c][0,\sqrt{c}][0,c]，因此我们可以使用「双指针」在 [0,c][0,\sqrt{c}][0,c] 范围进行扫描：
- a2+b2==ca^2 + b^2 == ca2+b2==c : 找到符合条件的
a和b，返回 truetruetrue - a2+b2<ca^2 + b^2 < ca2+b2<c : 当前值比目标值要小，
a++ - a2+b2>ca^2 + b^2 > ca2+b2>c : 当前值比目标值要大，
b--
代码：
class Solution { public boolean judgeSquareSum(int c) { int a = 0, b = (int)Math.sqrt(c); while (a <= b) { int cur = a * a + b * b; if (cur == c) { return true; } else if (cur > c) { b--; } else { a++; } } return false; } } 复制代码
- 时间复杂度：O(c)O(\sqrt{c})O(c)
- 空间复杂度：O(1)O(1)O(1)
费马平方和
费马平方和 : 奇质数能表示为两个平方数之和的充分必要条件是该质数被 4 除余 1 。
翻译过来就是：当且仅当一个自然数的质因数分解中，满足 4k+3 形式的质数次方数均为偶数时，该自然数才能被表示为两个平方数之和。
因此我们对 c 进行质因数分解，再判断满足 4k+3 形式的质因子的次方数是否均为偶数即可。
代码：
public class Solution { public boolean judgeSquareSum(int c) { for (int i = 2, cnt = 0; i * i <= c; i++, cnt = 0) { while (c % i == 0 && ++cnt > 0) c /= i; if (i % 4 == 3 && cnt % 2 != 0) return false; } return c % 4 != 3; } } 复制代码
- 时间复杂度：O(c)O(\sqrt{c})O(c)
- 空间复杂度：O(1)O(1)O(1)
我猜你问
- 三种解法复杂度都一样，哪个才是最优解呀？
前两套解法是需要「真正掌握」的，而「费马平方和」更多的是作为一种拓展。
你会发现从复杂度上来说，其实「费马平方和」并没有比前两种解法更好，但由于存在对 c 除质因数操作，导致「费马平方和」实际表现效果要优于同样复杂度的其他做法。但这仍然不成为我们必须掌握「费马平方和」的理由。
三者从复杂度上来说，都是 O(c)O(\sqrt{c})O(c) 算法，不存在最不最优的问题。
- 是否有关于「费马平方和」的证明呢？
想要看 莱昂哈德·欧拉 对于「费马平方和」的证明在 这里，我这里直接引用 费马 本人的证明：
我确实发现了一个美妙的证明，但这里空白太小写不下。
- 我就是要学「费马平方和」，有没有可读性更高的代码？
有的，在这里。喜欢的话可以考虑背过：
public class Solution { public boolean judgeSquareSum(int c) { for (int i = 2; i * i <= c; i++) { int cnt = 0; while (c % i == 0) { cnt++; c /= i; } if (i % 4 == 3 && cnt % 2 != 0) return false; } return c % 4 != 3; } } 复制代码
最后
这是我们「刷穿 LeetCode」系列文章的第 No.633 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
