LeetCode 367. 有效的完全平方数

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 百度
标签
数学 二分查找
目录

题目描述

✅ 367. 有效的完全平方数

题意分析

给定一个正整数 num，判断它是否是某个整数的平方，返回布尔值。注意题目明确禁止使用内置的开方函数——这句话是整道题的题眼，它把「一行 Math.sqrt」的路堵死，要求候选人自己实现搜索或迭代过程。

num 的上限是 $2^{31} - 1$，也就是 int 的最大值。这个约束透露了两件事：第一，答案的平方根最大约为 46341，搜索空间不算大但逐个枚举仍有四万多次；第二，也是更关键的，任何在 int 范围内计算「候选值的平方」的写法都会溢出——46341 的平方已经超过 int 上限。

真正可以利用的性质是单调性：在正整数范围内，x 越大 $x^2$ 越大，且严格递增。这意味着「$x^2$ 与 num 的大小关系」把整个搜索区间干净地切成了「偏小」和「偏大」两段，是可以对半砍的结构，而不必线性试探。

边界上：num 最小为 1，此时答案为真，搜索区间只有一个点；num 若为 2 或 3 这类夹在 1 和 4 之间的数，区间会收缩到空而不产生任何命中，必须让循环能正常退出并返回假。

解法：二分查找判定答案

核心思路

在正整数范围内，候选根 x 越大，x² 严格增大。因此比较 mid² 与 num 后，可以一次排除一半候选：平方偏小就向右找，平方偏大就向左找。相比逐个枚举到 √num，二分只需对数级比较，逻辑也比牛顿迭代更直接，适合作为面试主解法。

使用闭区间 [left, right]，并维护不变量：如果 num 存在整数平方根，那么该根始终在当前区间内。初始区间 [1, num] 显然包含所有可能的正整数根；若 mid² < num，由单调性可知 [left, mid] 都不可能是答案，令 left = mid + 1；若 mid² > num，同理令 right = mid - 1。每次都排除 mid，区间严格缩小。

正确性说明：命中 mid² == num 时，mid 就是整数平方根，返回 true 正确；未命中时，上述更新保持不变量。循环结束意味着 left > right，候选区间为空，由不变量可知不存在整数平方根，返回 false 正确。

num 最大为 2³¹ - 1，二分早期的 mid 可能接近十亿，mid * mid 会溢出 32 位整数。Java 必须用 long，Go 先把目标和边界转为 int64，再做乘法。

解题步骤

  • 初始化 left = 1、right = num，表示尚未排除的候选根。
  • 当 left <= right 时，用 mid = left + (right - left) / 2 取中点，并以 64 位整数计算 square = mid * mid。
  • square == num 时立即返回 true；偏小时令 left = mid + 1；偏大时令 right = mid - 1。
  • 区间收缩为空仍未命中，返回 false。

例如 num = 14 时，中点依次为 7、3、5、4，平方依次落在目标两侧，最终区间为空，返回 false。num = 1 时初始区间只有候选 1，第一轮即命中；num = 2147395600 = 46340² 也能正确返回 true，且 64 位乘法不会溢出。

代码实现

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1;
        long right = num;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            if (square == num) {
                return true;
            }
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

func isPerfectSquare(num int) bool {
	target := int64(num)
	left, right := int64(1), target

	for left <= right {
		mid := left + (right-left)/2
		square := mid * mid
		if square == target {
			return true
		}
		if square < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

复杂度分析

  • 时间复杂度：O(log n)。每轮至少排除当前候选区间的一半。
  • 空间复杂度：O(1)。只使用固定数量的整数变量。

关键点总结

  • 可二分的依据不是“有数组”，而是判定函数 x² 在候选值域上严格单调。
  • 闭区间写法必须配套使用 left <= right 与 mid ± 1，保证单点候选会被检查且循环必然结束。
  • 正确性的核心不变量是：若答案存在，它始终留在 [left, right] 中。
  • 中点公式防止边界相加溢出，平方则必须提升到 64 位后再计算。

易错点总结

  • 用 int 计算 mid * mid：num = 2147395600 时，二分过程中的大中点会发生 32 位溢出，比较方向随之错误。应先把参与乘法的变量提升为 64 位。
  • 闭区间却写 left < right：num = 1 时初始 left == right，唯一候选没有被检查就返回 false。
  • 更新为 left = mid 或 right = mid：num = 2 时可能反复得到同一个中点，区间不再缩小并形成死循环。
  • 把命中也当作普通收缩：num = 16、mid = 4 时若没有相等分支，会跳过唯一答案。要么命中立即返回，要么采用另一套“收缩后统一验证”的完整模板，不能混写。
  • Go 中混用 int 与 int64：square == num 无法编译；先保存 target := int64(num)，后续比较统一使用 int64。

相似题目

题目 难度 考察点
69. x 的平方根 简单 同样对值域二分，但要返回向下取整的根，命中失败时还需确定返回哪个边界
704. 二分查找 简单 二分对象是真实数组而非抽象值域，判据是元素比较而不是计算出来的函数值
35. 搜索插入位置 简单 未命中时必须返回插入下标，考察循环结束后 left 的语义而非直接返回布尔值
34. 在排序数组中查找元素的第一个和最后一个位置 中等 存在重复元素，需要写出左右两套边界收缩规则各跑一次
278. 第一个错误的版本 简单 判据由外部 API 给出且调用次数受限，重点在减少判定调用而非计算
33. 搜索旋转排序数组 中等 整体不单调，必须先判断哪半段有序才能决定往哪边收缩