LeetCode | 0633. Sum of Square Numbers平方数之和【Python】

LeetCode 0633. Sum of Square Numbers平方数之和【Easy】【Python】【双指针】

题目

英文题目链接

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a*a + b*b = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

翻译

中文题目链接

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a*a + b*b = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False

思路

双指针

a 指针从 0 开始，b 指针取 c 的平方根。然后分别相向移动，如果 a*a + b*b < c，让 a 加 1，如果 a*a + b*b > c，让 b 减 1。

时间复杂度：
$O\left(\sqrt{c}\right)$O(c ​)

Python代码

class Solution(object):
    def judgeSquareSum(self, c):
        """ :type c: int :rtype: bool """
        a = 0
        b = int(c**0.5)+1
        while a <= b:  # 假如 c = 2, 发现不加 = , 输出 False, 应该输出 True
            if a*a + b*b == c:
                return True
            elif a*a + b*b < c:
                a += 1
            else:
                b -= 1
        return False

代码地址

GitHub链接