网络异常，图片无法展示
|
「这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战」
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = 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 <= 231 - 1
通过分析题意可知，c 为大于等于 0 的整数，a、b 也是大于等于 0 的整数。
那我们想一个问题，就是如果 c 开平方之后的结果 n 是一个整数，是不是就说明 c=n²+0²
如果 n 不是整数，那么就说明 0 也不可能是 a、b中的一个，那么我们接下来可以去哪里继续查找可能的值呢？
只能是大于 0 且 小于等于 n 的整数，然后我们固定一个数，求得另一个数的平方和为 c-a²，再将这个结果开方，如果开方后的结果是一个整数，则说明这两个数的平方和为 c，返回 true 即可，反之继续查找
知道在上述区间中没有找到满足条件的组合，返回 false
至此，本题的解题思路就完成了，代码如下：
var judgeSquareSum = function(c) { let max = Math.sqrt(c); if(isInteger(max)) return true; // 依次判断大于0的整数是否是满足条件的一个整数 for(let i = 1;i<max;i++){ const target = Math.sqrt(c-Math.pow(i,2)) if(isInteger(target)) return true; } return false; // 判断传入数值是否是整数 function isInteger(num){ return Math.floor(num) === num } }; 复制代码
上述代码我们还有一个优化的空间
就是如果 i = 1的时候不满足条件，假设此时对应的 target是一个接近 10 的非整数，那么在后续 i 为 10的时候，找到对应的 target 肯定也不是一个整数
大概率是一个接近 1 的非整数，所以我们这里当 i 对应的 target 不满足条件的时候，i再走到接近 target的正整数是没有意义的
所以我们可以在 target 不满足条件后，将 max 调整为 target
如果通过上述描述没有讲清楚优化的逻辑，大家可以放开下方代码的 console 注释，给定一个 c=1002,查看调整 max=target 前后的循环次数即可。
var judgeSquareSum = function(c) { let max = Math.sqrt(c); if(isInteger(max)) return true; // 依次判断大于0的整数是否是满足条件的一个整数 for(let i = 1;i<max;i++){ const target = Math.sqrt(c-Math.pow(i,2)) // console.log(i,target) if(isInteger(target)) return true; max = target; } return false; // 判断传入数值是否是整数 function isInteger(num){ return Math.floor(num) === num } }; 复制代码
至此，我们就完成了leetcode-633-平方数之和
如有任何问题或建议，欢迎留言讨论！
