LeetCode每日一题633---平方数之和

一、题目描述

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

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
示例 2：

输入：c = 3
输出：false

提示：

0 <= c <= 231 - 1

二、解题思路

方法1 ：暴力法
如果存在符合条件的a，b，那么a和b一定在0和sqrt(c)之间。
最朴素的思路，就是先令a从0遍历到sqrt(c),那么b=sqrt（c-a*a） 然后看得到的b是否为整数 则符合条件。
需要注意的是，a的终止条件最好是i <= c / i，不要使用i * i <= c ，因为i * i可能会溢出

方法2 ：双指针法
另一种时间复杂度低的方式是双指针法：
先令a = 0，b=sqrt（c） 如果a*a + b * b > c 那么b--, 如果a*a + b * b< c 那么a++,

三、代码

1、暴力法

class Solution {
public:bool judgeSquareSum(int c) {if(c == 0){return true;}for(int a=1; a<=c/a;a++){double b = sqrt(c - a*a);if(b == (int) b){return true;}}return false; }
};

2、双指针法

class Solution {public boolean judgeSquareSum(int c) {int a = 0,b = (int)Math.sqrt(c);for(int i = a,j = b;i <= j;){if(i * i + j * j == c)return true;else if(i * i + j * j > c)j--;else if(i * i + j * j < c)i++;}return false;}
}