633. 平方数之和
题目描述
给定一个非负整数 c
,你要判断是否存在两个整数 a
和 b
,使得 a2 + b2 = c
。
示例 1:
输入:c = 5 输出:true 解释:1 * 1 + 2 * 2 = 5
示例 2:
输入:c = 3 输出:false
提示:
0 <= c <= 231 - 1
解法
方法一:数学 + 双指针
我们可以使用双指针的方法来解决这个问题,定义两个指针 $a$ 和 $b$,分别指向 $0$ 和 $\sqrt{c}$。在每一步中,我们会计算 $s = a^2 + b^2$ 的值,然后比较 $s$ 与 $c$ 的大小。如果 $s = c$,我们就找到了两个整数 $a$ 和 $b$,使得 $a^2 + b^2 = c$。如果 $s < c$,我们将 $a$ 的值增加 $1$,如果 $s > c$,我们将 $b$ 的值减小 $1$。我们不断进行这个过程直到找到答案,或者 $a$ 的值大于 $b$ 的值,返回 false
。
时间复杂度 $O(\sqrt{c})$,其中 $c$ 是给定的非负整数。空间复杂度 $O(1)$。
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|