How can binary search help with the Sum of Square Numbers problem?

Binary search can efficiently narrow down the possible values for the integers a and b by searching the range for valid square sums.

What’s the optimal time complexity for the Sum of Square Numbers problem?

The optimal time complexity is O(sqrt(c)) when using binary search or two-pointer approaches.

Are there any edge cases to consider when solving this problem?

Yes, especially when c is 0, where the solution is trivially true (since 0^2 + 0^2 = 0).

Can two-pointer or binary search be used to solve this problem efficiently?

Yes, both techniques are efficient for this problem. Binary search can be used to explore the possible squares, and two-pointer works well by checking sums incrementally.

How do I optimize my solution for the Sum of Square Numbers problem?

You can optimize your solution by limiting the search space using binary search or the two-pointer technique, both of which offer O(sqrt(c)) time complexity.

#633

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b ，使得 a 2 + b 2 = c 。示例 1：输入： c = 5 输出： true 解释： 1 * 1 + 2 * 2 = 5 示例 2：输入： c = 3 输出： false 提示： 0 31 - 1

数学双指针二分查找

题目描述

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

示例 1：

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

示例 2：

输入：c = 3
输出：false

提示：

0 <= c <= 2³¹ - 1

lightbulb

解题思路

方法一：数学 + 双指针

我们可以使用双指针的方法来解决这个问题，定义两个指针 $a$ 和 $b$ ，分别指向 $0$ 和 $\sqrt{c}$ 。在每一步中，我们会计算 $s = a^2 + b^2$ 的值，然后比较 $s$ 与 $c$ 的大小。如果 $s = c$ ，我们就找到了两个整数 $a$ 和 $b$ ，使得 $a^2 + b^2 = c$ 。如果 $s < c$ ，我们将 $a$ 的值增加 $1$ ，如果 $s > c$ ，我们将 $b$ 的值减小 $1$ 。我们不断进行这个过程直到找到答案，或者 $a$ 的值大于 $b$ 的值，返回 false。

时间复杂度 $O(\sqrt{c})$ ，其中 $c$ 是给定的非负整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's ability to apply binary search over a valid range efficiently.
question_mark
Assesses understanding of two-pointer techniques in algorithmic problem-solving.
question_mark
Evaluates the candidate's ability to recognize patterns in math-based problems.

warning

常见陷阱

外企场景

error
Failing to optimize the search space, leading to unnecessarily complex solutions.
error
Overcomplicating the problem and missing simpler solutions like binary search or two-pointer.
error
Not handling edge cases such as c = 0 correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the sum of squares must be divisible by a certain number?
arrow_right_alt
What if negative numbers were allowed for a and b?
arrow_right_alt
What if the problem asked for more than two squares to sum up to c?

help

常见问题

外企场景

继续练习

#1237 找出给定方程的正整数解 #611 有效三角形的个数 #658 找到 K 个最接近的元素