0633. 平方数之和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针

1. 📝 题目描述

• leetcode

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

---

示例 1：

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

示例 2：

输入：c = 3
输出：false

---

提示：

• 0 <= c <= 2^31 - 1

2. 🎯 s.1 - 双指针

c

#include <math.h>

bool judgeSquareSum(int c) {
    long a = 0, b = (long)sqrt((double)c);
    while (a <= b) {
        long sum = a * a + b * b;
        if (sum == c) return true;
        else if (sum < c) a++;
        else b--;
    }
    return false;
}

js

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function (c) {
  let a = 0,
    b = Math.floor(Math.sqrt(c))
  while (a <= b) {
    const sum = a * a + b * b
    if (sum === c) return true
    else if (sum < c) a++
    else b--
  }
  return false
}

py

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

• 时间复杂度：$O(\sqrt{c})$
• 空间复杂度：$O(1)$

算法思路：

• 初始化 a = 0、b = floor(sqrt(c))
• 若 a² + b² == c 则返回 true，小于则 a++，大于则 b--