本文主要是介绍【双指针法】【打卡第35天】leetCode之Java实现:633. 平方数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
2、题目分析
本题使用的是双指针解法。
可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
本题和 167. 两数之和 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。
本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。
因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。
知识补充：
① sqrt(int m)：对m进行开平方，sqrt(5) = 2，当然要取整数
② leetCode的测试用例范围比较大：所以最好是使用Long长整型
3、代码实现
/**双指针法求解*/
import java.util.*;
class Solution {public boolean judgeSquareSum(int c) {long a = 0, b = (long)Math.sqrt(c);while (a <= b) {long cur = a * a + b * b;if (cur == c) {return true;} else if (cur > c) {b--;} else {a++;}}return false;}
}这篇关于【双指针法】【打卡第35天】leetCode之Java实现:633. 平方数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
