Question

633. 平方数之和

English Version

题目描述

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

 

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

 

提示：

• 0 <= c <= 231 - 1

解法

方法一

class Solution:
  def judgeSquareSum(self, c: int) -> bool:
    a, b = 0, int(sqrt(c))
    while a <= b:
      s = a**2 + b**2
      if s == c:
        return True
      if s < c:
        a += 1
      else:
        b -= 1
    return False

class Solution {
  public boolean judgeSquareSum(int c) {
    long a = 0, b = (long) Math.sqrt(c);
    while (a <= b) {
      long s = a * a + b * b;
      if (s == c) {
        return true;
      }
      if (s < c) {
        ++a;
      } else {
        --b;
      }
    }
    return false;
  }
}

class Solution {
public:
  bool judgeSquareSum(int c) {
    long a = 0, b = (long) sqrt(c);
    while (a <= b) {
      long s = a * a + b * b;
      if (s == c) return true;
      if (s < c)
        ++a;
      else
        --b;
    }
    return false;
  }
};

func judgeSquareSum(c int) bool {
  a, b := 0, int(math.Sqrt(float64(c)))
  for a <= b {
    s := a*a + b*b
    if s == c {
      return true
    }
    if s < c {
      a++
    } else {
      b--
    }
  }
  return false
}

function judgeSquareSum(c: number): boolean {
  let a = 0,
    b = Math.floor(Math.sqrt(c));
  while (a <= b) {
    let sum = a ** 2 + b ** 2;
    if (sum == c) return true;
    if (sum < c) {
      ++a;
    } else {
      --b;
    }
  }
  return false;
}

use std::cmp::Ordering;
impl Solution {
  pub fn judge_square_sum(c: i32) -> bool {
    let c = c as i64;
    let mut left = 0;
    let mut right = (c as f64).sqrt() as i64;
    while left <= right {
      let num = left * left + right * right;
      match num.cmp(&c) {
        Ordering::Less => {
          left += 1;
        }
        Ordering::Greater => {
          right -= 1;
        }
        Ordering::Equal => {
          return true;
        }
      }
    }
    false
  }
}