What is the fastest way to check if a number is a perfect square in this problem?

Use binary search over the range 1 to num, comparing mid * mid with num at each step to find an exact integer square root.

Can I use sqrt or other math libraries?

No, built-in functions are prohibited. You must rely on integer arithmetic and binary search to detect perfect squares.

Why not use floating-point comparisons?

Floating-point operations can introduce rounding errors, causing incorrect results for large numbers. Integer arithmetic is precise for this problem.

How do I handle large numbers safely?

Ensure that mid * mid does not overflow by using data types that can store large integers or compare mid with num // mid instead of squaring.

What pattern does this problem follow?

It follows the binary search over valid answer space pattern, testing each candidate integer square root against the target number.

#367

Easy

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

LeetCode 题解工作台

有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。不能使用任何内置的库函数，如 sqrt 。示例 1：输入： num = 16 输出： true 解释…

数学二分查找

题目描述

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 <= num <= 2³¹ - 1

lightbulb

解题思路

方法一：二分查找

我们可以使用二分查找来解决这个问题。定义二分查找的左边界 $l = 1$ ，右边界 $r = num$ ，然后在 $[l, r]$ 的范围内查找满足 $x^2 \geq num$ 的最小整数 $x$ 。最后，如果 $x^2 = num$ ，则说明 $num$ 是一个完全平方数。

时间复杂度 $O(\log n)$ ，其中 $n$ 是给定的数字。空间复杂度 $O(1)$ 。

1

2

3

4

5

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = bisect_left(range(1, num + 1), num, key=lambda x: x * x) + 1
        return l * l == num

speed

复杂度分析

指标	值
时间	complexity is O(log(num)) because the binary search halves the search space each step. Space complexity is O(1) since only a few variables are needed regardless of input size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Confirm the candidate can implement binary search correctly over a numeric range.
question_mark
Check awareness of integer overflow risks when squaring numbers.
question_mark
Listen for an approach that avoids floating-point operations for exact perfect square detection.

warning

常见陷阱

外企场景

error
Attempting to use floating-point sqrt and comparing with rounding, which can fail for large num values.
error
Forgetting to handle num = 1 as a trivial perfect square.
error
Squaring mid without checking for overflow, leading to incorrect results or runtime errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if num is a perfect cube using the same binary search over cube roots.
arrow_right_alt
Return all perfect squares less than or equal to num using incremental binary search validation.
arrow_right_alt
Determine if a sequence of numbers contains any perfect squares efficiently using batch binary search.

help

常见问题

外企场景

继续练习

#400 第 N 位数字 #441 排列硬币 #268 丢失的数字