LeetCode 633. 平方数之和
题目描述
题意分析
判断非负整数
c是否能表示为两个整数的平方和。负数与其相反数的平方相同，所以只需找非负整数；交换两数也不影响结果，可以约定较小者在前。两数允许相等，也允许为 0。
解法：双指针
核心思路
[!blue]
平方项非负，因此任一候选的平方都不能超过
c，两数只能位于0到floor(sqrt(c))之间。非负数的平方随数值增大而增大，可以把这些平方看成一个无需实际构造的有序数组，用左右指针寻找目标和。令
left = 0、right = floor(sqrt(c))。若left² + right² < c，当前left即使配上剩余最大的right也不够，配更小的数只会更小，因此可以排除这个left，令它加一。若平方和> c，当前right即使配上剩余最小的left也过大，配更大的数仍会过大，因此排除这个right，令它减一。每次移动都排除一个不可能参与答案的端点，仍有解时不会越过它。平方和相等就找到答案；
left > right表示所有有序候选都已排除。两端相等仍是一种合法配对，所以循环条件必须保留等号。输入虽在 32 位有符号整数范围内，枚举到的两个平方之和仍可能超过该范围。代码从端点开始使用 Java 的
long或 Go 的int64，让乘法和加法都在宽整数中完成。
解题步骤
- 将左端设为 0，右端设为
sqrt(c)向下取整。- 在
left <= right时计算两端平方和，相等则返回true。- 平方和较小时只增加左端，较大时只减少右端。
- 两端交错后返回
false。c = 0时两端均为 0，第一轮就能确认答案；完全平方数也可以由左端的 0 配合右端得到。
代码实现
class Solution {
public boolean judgeSquareSum(int c) {
long left = 0;
long right = (long) Math.sqrt(c);
// 允许相同两数，端点重合仍要检查
while (left <= right) {
long sum = left * left + right * right;
if (sum == c) {
return true;
} else if (sum < c) {
// 当前左值配任何更小右值都不足，排除左值
left++;
} else {
// 当前右值配任何更大左值都超标，排除右值
right--;
}
}
return false;
}
}
import "math"
func judgeSquareSum(c int) bool {
left := int64(0)
right := int64(math.Sqrt(float64(c)))
target := int64(c)
// 允许相同两数，端点重合仍要检查
for left <= right {
sum := left*left + right*right
if sum == target {
return true
} else if sum < target {
// 当前左值配任何更小右值都不足，排除左值
left++
} else {
// 当前右值配任何更大左值都超标，排除右值
right--
}
}
return false
}
复杂度分析
- 时间复杂度：$O(\sqrt c+1)$。每轮至少让一个端点向内移动一步，初始区间只有 $\lfloor\sqrt c\rfloor+1$ 个候选。
- 空间复杂度：$O(1)$，只保存两个端点与平方和。
关键点总结
[!green]
- 候选两数允许相等，循环必须包含等号。
- 单调性建立在非负平方候选上。
易错点总结
[!yellow]
- 循环写成严格小于会漏掉二这样的等值配对。
- 左端从一开始，会漏掉零平方参与的答案。
- 先以窄整数乘法计算再转换，转换时已经可能溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 69. x 的平方根 | 简单 | 整数平方根确定枚举或双指针上界，本题还要寻找另一个平方补数。 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 平方数是有序序列，可把问题视为两个虚拟有序元素的目标和双指针。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！