双指针｜633. 平方数之和

2021 年 04 月 28 日 链接：https://leetcode-cn.com/problems/sum-of-square-numbers/

题目

描述

给定一个非负整数 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 <= 2^31 - 1

  解答

  思路

• 先有式子 x^2 + y^2 = c

• 从而可以设置循环，x 从 0 开始递增，y 从小于 c 的平方根的最大整数开始递减
• x = 0 、y = floor(sqrt(c))
• 当 left > right 停止循环，说明不存在
• 当 c - left^2 === right^2 返回 true 终止循环，说明值存在
  

  代码

  /**
  * @param {number} c
  * @return {boolean}
  */
  var judgeSquareSum = function(c) {
    let left = 0
    let right = Math.floor(Math.sqrt(c))
    while(left <= right){
        if(c - left ** 2 > right ** 2){
            left ++
        }
        else if(c - left ** 2 < right ** 2){
            right --
        }
        else{
            return true
        }
    }
    return false
  };