[LeetCode] 633. Sum of Square Numbers (JS)

內容目錄 隱藏

題目

給定一個非負整數 c ，判斷是否有兩個整數 a 和 b 使得 a² + b² = c 。

解法一

使用 for 迴圈

a, b 一定比 c 開平方還要小（或等於），所以可以從 c 開平方慢慢往回遍歷尋找最大的a
b²= c – a²
得出 b² 後開根號如果是整數就代表 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 是由 0² + 0² 組成，所以 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])

瀏覽量: 9