一、題目
LeetCode-633. 平方數(shù)之和
地址：https://leetcode-cn.com/problems/sum-of-square-numbers/
難度：中等
給定一個非負整數(shù) c ，你要判斷是否存在兩個整數(shù) 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 <= 2^31 - 1
二、解題思路
方法一：對a進行枚舉，同時使用sqrt函數(shù)看看是否能找到的整數(shù)b。
方法二： 雙指針，可以假設(shè) a≤b。初始時 a = 0，b = sqrt(c)。
如果a * a + b * b = c，返回true
如果a * a + b * b < c，左指針a+1
如果a * a + b * b > c，右指針b-1
當(dāng) a = b 時，如果 a 和 b不 滿足 a * a + b * b = c， 則說明不存在題目要求的解，返回false。
三、實現(xiàn)過程
方法一
c++
ps:需要特別注意0 <= c <= 2^31 - 1，防止a溢出要使用long
class Solution {
public:
bool judgeSquareSum(int c) {
for(long a = 0;a*a <= c;a++){
double b = sqrt(c-a*a);
if(b == (int)b){
return true;
}
}
return false;
}
};
PHP
class Solution {
/**
* @param Integer $c
* @return Boolean
*/
function judgeSquareSum($c) {
for($a = 0;$a*$a <= $c;$a++){
$b = sqrt($c-$a*$a);
if($b == intval($b)){
return true;
}
}
return false;
}
}
JavaScript
/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
for(var a = 0;a*a <= c;a++){
const b = Math.sqrt(c-a*a);
if(b === parseInt(b)){
return true;
}
}
return false;
};
方法二
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;
}
if(sum > c){
right--;
}else{
left++;
}
}
return false;
}
};
PHP
class Solution {
/**
* @param Integer $c
* @return Boolean
*/
function judgeSquareSum($c) {
$left = 0;
$right = intval(sqrt($c));
while($left <= $right){
$sum = $left*$left + $right*$right;
if($sum == $c){
return true;
}
if($sum > $c){
$right--;
}else{
$left++;
}
}
return false;
}
}
JavaScript
/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
var left = 0;
var right = Math.floor(Math.sqrt(c));
while(left <= right){
const sum = left*left + right*right;
if (sum === c) {
return true;
}
if (sum > c) {
right--;
} else {
left++;
}
}
return false;
};
四、小結(jié)
本題與算法入門-167. 兩數(shù)之和 II - 輸入有序數(shù)組類似，可以使用雙指針進行求解。
另外本題還可以費馬平方和定理進行求解，因本人對數(shù)學(xué)方法理解不到為，這里沒給出實現(xiàn)過程。
一個非負整數(shù) c 如果能夠表示為兩個整數(shù)的平方和，當(dāng)且僅當(dāng) c 的所有形如 4k + 34k+3 的質(zhì)因子的冪均為偶數(shù)。
