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

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

題目

給定一個非負整數 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

解法二(推薦)

使用雙指針來解。

  1. 初始化雙指針
    • left 從 0 開始,代表較小的平方數。
    • right 從 根號c​ 開始,代表較大的平方數。
  2. 迴圈遍歷
    • left 小於或等於 right 時,計算 leftright 的平方和。
    • 如果平方和等於 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
};
image 3

兩種解法的Runtime和Memory Usage差不了太多。left 和 right 兩個指針最多各自移動 [math]\sqrt{c}[/math] 次,因為指針移動的範圍是從 0 到 [math]\sqrt{c}[/math]。所以此解法的時間複雜度為 O([math]\sqrt{c}[/math])

guest

0 評論
內聯回饋
查看全部評論