題目
給定一個非負整數 c ，判斷是否有兩個整數 a 和 b 使得 a2 + b2 = c 。
解法一
使用 for 迴圈
- a, b 一定比 c 開平方還要小（或等於），所以可以從 c 開平方慢慢往回遍歷尋找最大的a
- b2= c – a2
- 得出 b2 後開根號如果是整數就代表 c 是兩數平方數之和
/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
let result = false
for (let a = Math.floor(Math.sqrt(c)); a >= 0; a--) {
const b_square = c - Math.pow(a, 2)
if (Number.isInteger(Math.sqrt(b_square)))
result = true
}
return result
};要注意的是 0 是由 02 + 02 組成，所以 0 回傳的是 true
解法二(推薦)
使用雙指針來解。
- 初始化雙指針
left從 0 開始，代表較小的平方數。right從 根號c 開始，代表較大的平方數。
- 迴圈遍歷
- 當
left小於或等於right時，計算left和right的平方和。 - 如果平方和等於
c，立即返回true。 - 如果平方和小於
c，增大left以增加平方和。 - 如果平方和大於
c，減小right以減小平方和。
- 當
/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
let left = 0
let right = Math.floor(Math.sqrt(c))
while(left <= right) {
let sum = Math.pow(left, 2) + Math.pow(right, 2)
if (sum === c) return true
else if (sum < c) left++
else right--
}
return false
};
兩種解法的Runtime和Memory Usage差不了太多。left 和 right 兩個指針最多各自移動 [math]\sqrt{c}[/math] 次，因為指針移動的範圍是從 0 到 [math]\sqrt{c}[/math]。所以此解法的時間複雜度為 O([math]\sqrt{c}[/math])
