633. 平方数之和(Medium)

题目描述

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

样例

Input：c = 5
Output：true
解释：1 * 1 + 2 * 2 = 5

题解

同 167.两数之和 II - 输入有序数组(Easy) 一样的思想，使用双指针指向首尾，然后向中间搜索。

双指针解决搜索问题比较擅长

Python示例

import math
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, math.ceil(math.sqrt(c)) # 使用 sqrt 可以使得复杂度降低为 O(sqrt(n))
        while left <= right:
            if left ** 2 + right ** 2 < c:
                left += 1
            elif left ** 2 + right ** 2 > c:
                right -= 1
            else:
                return True 
        return False