LeetCode日常-中等-633. 平方数之和
本文最后更新于:2021年5月4日 中午
题目
给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
方法一:使用 sqrt 函数
在枚举 a 的同时,使用 sqrt
函数找出 b
1 |
|
复杂度分析
时间复杂度:O(sqrt(c)) 枚举 a 的时间复杂度为 O(sqrt(c)),对于每个 a 的值,可在 O(1) 的时间内寻找 b
空间复杂度:O(1)
方法二:双指针
左右向中间靠拢的双指针
1 |
|
为什么不会错过答案?
举个例子,c = 18,初始化low = 0,high = 4,那么看如下矩阵:
矩阵沿主对角线对称 low<=high
其中的元素表示 low²+high²
的值; 黄色格子表示当前的 low²+high²
; 绿色格子表示目标 c
; low++
相当于让黄色格子下移; high--
则相当于让黄色格子左移;
每一列从上到下升序,每一行从左到右升序;
查找的过程具有如下性质:
- 初始化时黄色格子必定在矩阵的右上角
- 每次比较 low²+high²low 和
c
可以排除矩阵的一行或一列
由于以上性质,当前黄色格子的上方和右边的所有元素一定是已经被排除的,所以黄色格子在搜索过程中只有两种行为:
- 小于
c
:左边的元素都小于当前元素,只能下移,相当于low++
此时排除的是黄色格子以及左边同行的元素,都小于c
,所以不会错过正确答案 - 大于
c
:下面的元素都大于当前元素,只能左移,相当于high--
此时排除的是黄色格子以及下方同列的元素,都大于c
,所以不会错过正确答案
参考:
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!