LeetCode 第367题：有效的完全平方数

📖 文章摘要

本文详细解析LeetCode第367题“有效的完全平方数”，这是一道数学和二分查找问题。文章提供了基于二分查找的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学问题解决能力的读者。

核心知识点： 二分查找、数学、完全平方数 难度等级： 简单 推荐人群： 具有基础算法知识，想要提升数学问题解决能力的程序员

题目描述

给定一个正整数 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^31 - 1

解题思路

本题可以使用二分查找解决：

1. 在[1, num]范围内查找平方等于num的数
2. 如果找到，返回true
3. 如果没找到，返回false

时间复杂度： O(log n) 空间复杂度： O(1)

🎯 算法流程演示

图解思路

二分查找过程

步骤	左边界	右边界	中间值	平方值	说明
1	1	16	8	64	64 > 16，右边界=7
2	1	7	4	16	找到答案

特殊情况

情况	处理方式	说明
num = 0	返回true	0是0的平方
num = 1	返回true	1是1的平方
num < 0	返回false	负数不是完全平方数

代码实现

C# 实现

public class Solution {
    public bool IsPerfectSquare(int num) {
        if (num < 2) return true;
        
        long left = 2;
        long right = num / 2;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            }
            
            if (square > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return false;
    }
}

Python 实现

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True
            
        left = 2
        right = num // 2
        
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            
            if square == num:
                return True
                
            if square > num:
                right = mid - 1
            else:
                left = mid + 1
                
        return False

C++ 实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true;
        
        long left = 2;
        long right = num / 2;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            }
            
            if (square > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return false;
    }
};

执行结果

C# 实现

• 执行用时：36 ms
• 内存消耗：14.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：13.2 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：5.9 MB

性能对比

语言	执行用时	内存消耗	特点
C++	0 ms	5.9 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	36 ms	14.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用二分查找优化搜索效率
2. 💡 处理整数溢出问题
3. 🔍 处理特殊情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未处理整数溢出
2. 🚫 未处理特殊情况
3. 🚫 二分查找边界错误
4. 🚫 使用内置sqrt函数

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
二分查找	O(log n)	O(1)	高效，实现简单	需要处理溢出
牛顿迭代	O(log n)	O(1)	收敛更快	实现较复杂

相关题目

• LeetCode 69. x 的平方根 - 简单
• LeetCode 633. 平方数之和 - 中等
• LeetCode 279. 完全平方数 - 中等

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第367题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！