LeetCode: Sum of Square Numbers
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
方法一：
简单粗暴，嵌套依次遍历, 时间复杂度O(n^2)
I/O : 2147483641 // => (测试超时)
Detail -> Time Limit Exceeded
var judgeSquareSum = function(c) {
let sq = Math.sqrt(c)
for(let i = 0; i <= sq; i++) {
for(let j = i; j <= sq; j++) {
let pdt = i ** 2 + j ** 2
if(pdt === c) {
return true
} else if(pdt > c) {
break
}
}
}
return false
};
方法二：
二分法，先取 0，sqrt(c) ,在逐步往中间缩小范围，时间复杂度 O(n)
I/O : 2147483641 // => false
Detail -> cases: 124, Runtime: 68 ms
var judgeSquareSum = function(c) {
let b = Math.sqrt(c) | 0
let a = 0
while(a <= b) {
if (a * a + b * b < c) {
a--
} else if (a * a + b * b === c) {
return true
} else {
b--
}
}
return false
};
