Atrist

# 平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 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 <= 231 - 1

# 分析

对于给定的非负整数 c，需要判断是否存在整数 a 和 b，使得 a^2 + b^2 = c。

所有问题的通用解法 -> 暴力求解。

# 暴力解法

  • a --> sqrt(c)
  • b --> ? = sqrt(c - a*a)
var judgeSquareSum = function(c) {
  for(let a  =0; a*a <=c ;a++){
    const b = Math.sqrt(c - a*a)
    if(b === parseInt(b)) return true
  }
  return false
}

# 双指针优化(官方题解)

a取0, b取 sqrt(c), 开始遍历。

  • a^2 + b^2 = c, return true
  • a^2 + b^2 < c, a + 1
  • a^2 + b^2 > c, b - 1

当 a === b, return false

var judgeSquareSum = function(c) {
  let left =0 
  let right = parseInt(Math.sqrt(c))
  while(left<=right){
    let res = left*left + right*right
    if(res === c) return true
    else if(res > c) right--
    else left++
  }
  return false
};

# 参考资料