搭建一个公司网站,做网站公司销售开场白,阿里云网站建设方案书是什么,做美食类网站现状633. 平方数之和
2024.9.11
题目
给定一个非负整数 c #xff0c;你要判断是否存在两个整数 a 和 b#xff0c;使得 a2 b2 c 。
0 c 2的31次方 - 1
示例
示例 1#xff1a;
输入#xff1a;c 5
输出#xff1a;true
解释#xff1a;1 * 1 2 * 2 5示…633. 平方数之和
2024.9.11
题目
给定一个非负整数 c 你要判断是否存在两个整数 a 和 b使得 a2 b2 c 。
0 c 2的31次方 - 1
示例
示例 1
输入c 5
输出true
解释1 * 1 2 * 2 5示例 2
输入c 3
输出false反思
1.不要想当然的认为这道题有一致的解法虽然也可以用某种方式去做但很可能有更简单的方式。
2.千万注意题目中给值的边界如本题0 c 2的31次方 前后两个边界都要考虑一个是ab均有可能为0另一个是ab都有可能不能被int存放。
题解1-square
将数组nums的值和它对应的索引存入哈希表作为键值对利用哈希表查询时间复杂度为O(1)查询nums[i]是否存在。
class Solution {
public:bool judgeSquareSum(int c) {for (long a 0; a * a c; a) {long b_squared c - a * a;long b std::sqrt(b_squared);if (b * b b_squared) { // 如果 b 是整数那么 b_squared 是完全平方数return true;}}return false;}
};题解2-双指针
来自力扣官方题解
不失一般性可以假设 a≤b。初始时 a0b更号c 进行如下操作
class Solution {
public:bool judgeSquareSum(int c) {long left 0;long right (int)sqrt(c);while (left right) {long sum left * left right * right;if (sum c) {return true;} else if (sum c) {right--;} else {left;}}return false;}
};
