LeetCode 367. 有效的完全平方数
题目描述
题意分析
判断正整数
num是否恰好等于某个整数的平方，不能调用开方函数。要求精确相等，而不是只找到平方根向下取整后的结果。候选整数根至少为
1，至多为num。正整数的平方随数值严格增大，因此可以直接对候选根的取值范围二分，不需要创建数组，也不需要使用浮点数近似计算。
解法：二分查找判定答案
核心思路
[!blue]
用闭区间
[left, right]保存还可能成为整数平方根的候选，初始为[1, num]。每轮计算中点及其平方，比较它与目标的关系。平方等于
num时已经找到整数根，立即返回真。平方小于目标时，中点及更小的数的平方都不够大，可以令left = mid + 1；平方大于目标时，中点及更大的数都不可能命中，令right = mid - 1。每次比较都排除已经确定不合适的一半，若整数根存在，它始终留在区间内。区间只剩一个候选时也必须检查，因此循环使用
left <= right；两端交错说明所有候选都已排除，返回假。二分初始上界是
num，中间候选可能远大于最终平方根，因此计算平方前就要使用 64 位类型。代码直接把左右边界和中点设为宽整数，保证乘法本身不会先在 32 位中溢出，再把错误结果转换成宽整数。
解题步骤
- 用 64 位整数初始化
left = 1、right = num。- 区间非空时，计算中点
mid和它的平方。- 平方相等返回
true；偏小则移到右半边，偏大则移到左半边，两个分支都排除中点。- 区间为空后仍未命中，返回
false。
代码实现
class Solution {
public boolean isPerfectSquare(int num) {
// 先提升为 64 位，后续平方在同一类型内计算。
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 {
// 先提升为 64 位，避免平方乘法溢出。
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(num+1))$，每轮排除约一半候选。
- 空间复杂度：$O(1)$，只保存左右边界和中间结果。
关键点总结
[!green]
- 单调性：二分的是候选根的取值范围，不需要先有一个数组。
- 区间配套：闭区间对应
<=和mid ± 1。- 乘法位宽：先提升操作数，再计算平方。
易错点总结
[!yellow]
- 乘法之后才转换类型：32 位平方可能已经溢出，应先提升操作数的类型。
- 循环使用严格小于：最后一个候选也可能是平方根，闭区间要包含两端相等的情况。
- 更新仍保留中点：中点已确定不匹配，继续保留可能让区间不再缩小。
- 返回最接近的整数根就算成功：目标可能位于相邻整数平方之间，必须真正命中相等条件。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 69. x 的平方根 | 简单 | 整数平方根求出后可检查平方是否恰好相等，本题只返回是否为完全平方。 |
| 319. 灯泡开关 | 中等 | 灯泡最后亮起当且仅当编号为完全平方数，因子配对解释了平方数的特殊性。 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 在有序或具有单调判定的区间进行边界二分；本题检查平方根边界是否精确命中，该题定位等于目标值的左右边界。 |
| 35. 搜索插入位置 | 简单 | 在有序或具有单调判定的区间进行边界二分；本题检查平方根边界是否精确命中，该题寻找第一个不小于目标的位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！