华为
最近不少同学指出，华为计算开始大规模 OC 了，而具体的书面 Offer 则是 OC 后的一周内发送。
不过话说回来，这两个对接时间点也是让人头皮发麻。
又是晚上 10:30，又是中午 12:30，华为 HR 不休息的吗？还是想暗示些什么
但有得选总比 0Offer 要好，尤其是这个时间点，很多大厂流程都走完了，少部分的公司可能还有补录机会，但你要考虑清楚，为什么现在的招聘市场明明是供过于求，某些公司却仍然要进行"补录"呢？或许相比这些公司，华为至少还相对安全，而且在某些地区，华为员工还有着特殊的光环 🤣🤣🤣
对此，你怎么看？
...
回归主题。
来一道和「华为」相关的算法题。
题目描述
平台：LeetCode
题号：633
给定一个非负整数 c，你要判断是否存在两个整数 a 和 b，使得 。
示例 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
提示：
基本分析
根据等式 ，可得知 a 和 b 的范围均为 。
基于此我们会有以下几种做法。
枚举
我们可以枚举 a ，边枚举边检查是否存在 b 使得等式成立。
这样做的复杂度为 。
Java 代码：
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;
}
}
C++ 代码：
class Solution {
public:
bool judgeSquareSum(int c) {
int maxv = sqrt(c);
for (int a = 0; a <= maxv; a++) {
int b = sqrt(c - a * a);
if (a * a + b * b == c) return true;
}
return false;
}
};
Python 代码：
class Solution:
def judgeSquareSum(self, c: int) -> bool:
maxv = int(math.sqrt(c))
for a in range(maxv + 1):
b = int(math.sqrt(c - a * a))
if a * a + b * b == c:
return True
return False
TypeScript 代码：
function judgeSquareSum(c: number): boolean {
const maxv = Math.floor(Math.sqrt(c));
for (let a = 0; a <= maxv; a++) {
const b = Math.floor(Math.sqrt(c - a * a));
if (a * a + b * b === c) return true;
}
return false;
};
时间复杂度： 空间复杂度：
双指针
由于 a 和 b 的范围均为 ，因此我们可以使用「双指针」在 范围进行扫描：
: 找到符合条件的 a和b，返回: 当前值比目标值要小， a++: 当前值比目标值要大， b--
Java 代码：
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;
}
}
C++ 代码：
class Solution {
public:
bool judgeSquareSum(int c) {
int a = 0, b = sqrt(c);
while (a <= b) {
long cur = a * a * 1L + b * b;
if (cur == c) return true;
else if (cur > c) b--;
else a++;
}
return false;
}
};
Python 代码：
class Solution:
def judgeSquareSum(self, c: int) -> bool:
a, b = 0, int(math.sqrt(c))
while a <= b:
cur = a * a + b * b
if cur == c:
return True
elif cur > c:
b -= 1
else:
a += 1
return False
TypeScript 代码：
function judgeSquareSum(c: number): boolean {
let a = 0, b = Math.floor(Math.sqrt(c));
while (a <= b) {
let cur = a * a + b * b;
if (cur === c) return true;
else if (cur > c) b--;
else a++;
}
return false;
};
时间复杂度： 空间复杂度：
费马平方和
费马平方和 : 奇质数能表示为两个平方数之和的充分必要条件是该质数被 4 除余 1 。
翻译过来就是：当且仅当一个自然数的质因数分解中，满足 4k+3 形式的质数次方数均为偶数时，该自然数才能被表示为两个平方数之和。
因此我们对 c 进行质因数分解，再判断满足 4k+3 形式的质因子的次方数是否均为偶数即可。
Java 代码：
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;
}
}
C++ 代码：
class Solution {
public:
bool 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;
}
};
Python 代码：
class Solution:
def judgeSquareSum(self, c: int) -> bool:
for i in range(2, int(c**0.5) + 1, 1):
cnt = 0
while c % i == 0:
c //= i
cnt += 1
if i % 4 == 3 and cnt % 2 != 0:
return False
return c % 4 != 3
TypeScript 代码：
function judgeSquareSum(c: number): boolean {
for (let 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;
};
时间复杂度： 空间复杂度：
我猜你问
三种解法复杂度都一样，哪个才是最优解呀？
前两套解法是需要「真正掌握」的，而「费马平方和」更多的是作为一种拓展。
你会发现从复杂度上来说，其实「费马平方和」并没有比前两种解法更好，但由于存在对 c 除质因数操作，导致「费马平方和」实际表现效果要优于同样复杂度的其他做法。但这仍然不成为我们必须掌握「费马平方和」的理由。
三者从复杂度上来说，都是 算法，不存在最不最优的问题。
是否有关于「费马平方和」的证明呢？
想要看 莱昂哈德·欧拉 对于「费马平方和」的证明在 [维基百科: 费马平方和定理]，我这里直接引用 费马 本人的证明：
❝我确实发现了一个美妙的证明，但这里空白太小写不下。
❞
我就是要学「费马平方和」，有没有可读性更高的代码？
有的，在这里。喜欢的话可以考虑背过：
Java 代码：
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 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
