广水市建设局网站,电商网站用什么做最好,有空间站的国家,效果图制作属于什么经营范围1、题目描述
给定一个非负整数 c #xff0c;你要判断是否存在两个整数 a 和 b#xff0c;使得 a2 b2 c 。 示例 1#xff1a;
输入#xff1a;c 5
输出#xff1a;true
解释#xff1a;1 * 1 2 * 2 5示例 2#xff1a;
输入#xff1a;c 3
输出#xff1a;f…1、题目描述
给定一个非负整数 c 你要判断是否存在两个整数 a 和 b使得 a2 b2 c 。 示例 1
输入c 5
输出true
解释1 * 1 2 * 2 5示例 2
输入c 3
输出false
提示
0 c 231 - 1 2、代码
class Solution {
public:bool judgeSquareSum(int c) {// 定义两个指针 a 和 b// a 从 0 开始b 从 sqrt(c) 开始long a 0; // 使用 long 防止溢出long b static_castlong(sqrt(c)); // b 初始化为 c 的平方根// 双指针法a 从左向右移动b 从右向左移动while (a b) {// 计算当前 a^2 b^2 的值auto sum a * a b * b;if (sum c) {// 如果 sum 大于 c说明 b 的值太大了需要减小 b--b;} else if (sum c) {// 如果 sum 小于 c说明 a 的值太小了需要增大 aa;} else {// 如果 sum 等于 c找到了符合条件的 a 和 b返回 truereturn true;}}// 如果循环结束仍未找到符合条件的 a 和 b返回 falsereturn false;}
}; 3、解题思路 数学性质 如果存在两个整数 a 和 b 满足 a^2 b^2 c那么 a 和 b 的平方值一定在 [0, c] 范围内。因此我们可以通过枚举一个变量如 a并计算另一个变量如 b是否满足条件。 双指针法 使用两个指针 a 和 b分别从 0 和 sqrt(c) 开始移动。计算当前的平方和 sum a^2 b^2 如果 sum c说明找到了符合条件的 a 和 b返回 true。如果 sum c说明需要增大 a即让 a。如果 sum c说明需要减小 b即让 b--。 当 a b 时结束循环返回 false。 时间复杂度 由于 a 和 b 分别从两端向中间移动最多需要遍历 O(sqrt(c)) 次因此时间复杂度为 O(sqrt(c))。
