LeetCode日常-中等-633. 平方数之和

本文最后更新于：2021年5月4日 中午

题目

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

示例 1:

1
2
3
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

1
2
输入：c = 3
输出：false

示例 3：

1
2
输入：c = 4
输出：true

方法一：使用 sqrt 函数

在枚举 a 的同时，使用 sqrt 函数找出 b 

1
2
3
4
5
6
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        for a in range(int(sqrt(c)) + 1):
            if sqrt(c - a**2) % 1 == 0:
                return True
        return False

复杂度分析

时间复杂度：O(sqrt(c)) 枚举 a 的时间复杂度为 O(sqrt(c))，对于每个 a 的值，可在 O(1) 的时间内寻找 b
空间复杂度：O(1)

方法二：双指针

左右向中间靠拢的双指针 

1
2
3
4
5
6
7
8
9
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        low, high = 0, int(c**0.5)
        while low<=high:
            sumOf = low*low+high*high
            if sumOf==c: return True
            elif sumOf<c: low += 1
            else: high -= 1
        return False

为什么不会错过答案？

举个例子，c = 18，初始化low = 0，high = 4，那么看如下矩阵：

矩阵沿主对角线对称 low<=high其中的元素表示 low²+high² 的值; 黄色格子表示当前的 low²+high²; 绿色格子表示目标 c; low++相当于让黄色格子下移; high--则相当于让黄色格子左移;
每一列从上到下升序，每一行从左到右升序;
查找的过程具有如下性质：

  1. 初始化时黄色格子必定在矩阵的右上角
  2. 每次比较 low²+high²low 和 c 可以排除矩阵的一行或一列

由于以上性质，当前黄色格子的上方和右边的所有元素一定是已经被排除的，所以黄色格子在搜索过程中只有两种行为：

  • 小于 c ：左边的元素都小于当前元素，只能下移，相当于 low++
    此时排除的是黄色格子以及左边同行的元素，都小于 c ，所以不会错过正确答案
  • 大于 c ：下面的元素都大于当前元素，只能左移，相当于 high--
    此时排除的是黄色格子以及下方同列的元素，都大于 c ，所以不会错过正确答案

参考：

Python LeetCode 双指针

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！