0367. Valid Perfect Square.md

题目描述

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Output: true

Example 2:

Input: 14
Output: false

我的思路

首先想到遍历1到num/2的所有整数，一个一个判断。尝试之后，果然Time Limit Exceeded。

暴力方式肯定不行，想想平方数有什么特殊的性质。想到一条：1+3+5+7+....+(2n-1)=n² ，用这条性质入手，问题迎刃而解。

代码

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1:
            return True

        for i in range(1, num, 2):
            num = num - i
            if num == 0:
                return True
            if num < 0:
                return False

• 复杂度：O(n)