leetcode 633. 平方数之和（双指针）—golang版本 | Go主题月

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

示例 1：

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

输入：c = 3
输出：false
示例 3：

输入：c = 4
输出：true
示例 4：

输入：c = 2
输出：true
示例 5：

输入：c = 1
输出：true
 

提示：

0 <= c <= 231 – 1

解题思路

维护l，r两个元素值,l=0,r=sqrt(c),满足了l<=r条件,当ll+rr小于目标值，就需要移动左指针。当ll+rr大于目标值，说明元素太大了，就需要移动右指针。

原理

相当于每次固定一个右边界，然后收缩左边界。
为什么每次左指针不从1开始遍历，而是从上次的左指针开始？
因为每次更换右边界的条件是ll+rr>c, 这证明当前两个左指针的平方和太大了，所以需要换一个更小的右指针。那左指针前面的值为什么不行呢？

例如l-1，因为l是由l-1转移来的，而l-1转移到l的条件是l*l+r-r<c(注意：这里的r是缩减边界前的r))，在r更大的情况下，l-1产生的平方和都是偏小了，而现在又边界还收缩了，产生的平方和就更小了，所以根本不需要从1重新遍历一次，直接从左指针开始就可以了。

代码

func judgeSquareSum(c int) bool {
	l,r:=0,int(math.Sqrt(float64(c)))
	for l<=r {
		cur:=l*l+r*r
		if cur==c{
			return true
		}else if cur<c{
			l++
		}else {
			r--
		}
	}
	return false
	

}
复制代码

复杂度分析

时间复杂度：O(sqrt(c))。最坏情况下 l 和 r 一共枚举了 0 到 sqrt(c)
里的所有整数。

空间复杂度：O(1)。