633. 平方数之和-LeetCode(C++)

633. 平方数之和

2024.9.11
题目

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

• 0 <= c <= 2的31次方 - 1
  

示例

示例 1：

1. 输入：c = 5
2. 输出：true
3. 解释：1 * 1 + 2 * 2 = 5

复制代码

示例 2：

1. 输入：c = 3
2. 输出：false

复制代码

反思

1.不要想固然的认为这道题有一致的解法，固然也可以用某种方式去做，但很大概有更简单的方式。
2.千万注意题目中给值的边界，如本题0 <= c <= 2的31次方 ，前后两个边界都要考虑，一个是ab均有大概为0，另一个是ab都有大概不能被int存放。
题解1-square

将数组nums的值和它对应的索引存入哈希表作为键值对，利用哈希表查询时间复杂度为O(1)，查询nums是否存在。

1. class Solution {
2. public:
3.     bool judgeSquareSum(int c) {
4.         for (long a = 0; a * a <= c; ++a) {
5.             long b_squared = c - a * a;
6.             long b = std::sqrt(b_squared);
7.             if (b * b == b_squared) { // 如果 b 是整数，那么 b_squared 是完全平方数
8.                 return true;
9.             }
10.         }
11.         return false;
12.     }
13. };

复制代码

题解2-双指针

来自力扣官方题解
不失一般性，可以假设 a≤b。初始时 a=0，b=更号c ，举行如下操作：

1. class Solution {
2. public:
3.     bool judgeSquareSum(int c) {
4.         long left = 0;
5.         long right = (int)sqrt(c);
6.         while (left <= right) {
7.             long sum = left * left + right * right;
8.             if (sum == c) {
9.                 return true;
10.             } else if (sum > c) {
11.                 right--;
12.             } else {
13.                 left++;
14.             }
15.         }
16.         return false;
17.     }
18. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。