367. 有效的完全平方数
题目描述
输入一个正整数 num。如果存在某个整数 t 使得 t * t == num，就说 num 是完全平方数。
是完全平方数返回 true，否则返回 false。
不许调用 sqrt 这类库函数。
示例 1
输入：num = 16 输出：true
解释：4 * 4 = 16。
示例 2
输入：num = 14 输出：false
解释：14 的平方根约为 3.742，不是整数。
数据范围
1 <= num <= 2^31 - 1
解题思路
x² 随 x 单调递增，所以可以在 [1, num] 上二分。取 mid，算 mid²：等于 num 就找到了；小于 num 说明平方根在右边；大于 num 说明在左边。区间空了还没找到，就不是完全平方数。
为什么正确
如果存在整数 x 使 x² = num，那么 x 一定在 [lo, hi] 中。
复杂度分析
时间 O(log num)，空间 O(1)。
易错点
mid 可达 2^30 左右，mid² 会超出 32 位整数，C++/Java 里要用 long long / long。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isPerfectSquare(self, num: int) -> bool:
lo, hi = 1, num
while lo <= hi:
mid = (lo + hi) // 2
sq = mid * mid
if sq == num:
return True
if sq < num:
lo = mid + 1
else:
hi = mid - 1
return Falseclass Solution {
public boolean isPerfectSquare(int num) {
long lo = 1, hi = num;
while (lo <= hi) {
long mid = (lo + hi) / 2;
long sq = mid * mid;
if (sq == num) {
return true;
}
if (sq < num) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}
}class Solution {
public:
bool isPerfectSquare(int num) {
long long lo = 1, hi = num;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
long long sq = mid * mid;
if (sq == num) {
return true;
}
if (sq < num) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}
};func isPerfectSquare(num int) bool {
lo, hi := 1, num
for lo <= hi {
mid := (lo + hi) / 2
sq := mid * mid
if sq == num {
return true
}
if sq < num {
lo = mid + 1
} else {
hi = mid - 1
}
}
return false
}var isPerfectSquare = function(num) {
let lo = 1, hi = num;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
const sq = mid * mid;
if (sq === num) {
return true;
}
if (sq < num) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
};function isPerfectSquare(num: number): boolean {
let lo = 1, hi = num;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
const sq = mid * mid;
if (sq === num) {
return true;
}
if (sq < num) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}其他解法
二分查找在 [1, num] 内缩小范围，每步减半；牛顿迭代利用切线逼近根，接近根时每步有效位数翻倍，迭代次数更少。
解法 2：牛顿迭代法 时间 O(log n)，空间 O(1)
求 x² = num 的正根。从 x = num 出发，反复用切线与 x 轴的交点更新 x = (x + num / x) / 2（整数除法），直到 x² 不再大于 num。此时 x 就是 √num 向下取整，再判断 x² 是否等于 num。
收敛速度接近二次，实际迭代次数通常比二分少。需要一点微积分背景，并且要留意 x * x 可能超出 32 位整数范围。
class Solution:
def isPerfectSquare(self, num: int) -> bool:
x = num
while x * x > num:
x = (x + num // x) // 2
return x * x == numclass Solution {
public boolean isPerfectSquare(int num) {
long x = num;
while (x * x > num) x = (x + num / x) / 2;
return x * x == num;
}
}class Solution {
public:
bool isPerfectSquare(int num) {
long long x = num;
while (x * x > num) x = (x + num / x) / 2;
return x * x == num;
}
};func isPerfectSquare(num int) bool {
x := num
for x*x > num {
x = (x + num/x) / 2
}
return x*x == num
}var isPerfectSquare = function(num) {
let x = num;
while (x * x > num) x = Math.floor((x + Math.floor(num / x)) / 2);
return x * x === num;
};function isPerfectSquare(num: number): boolean {
let x = num;
while (x * x > num) x = Math.floor((x + Math.floor(num / x)) / 2);
return x * x === num;
}