給定一個非負整數?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?,滿足了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*rif cur==c{return true}else if cur<c{l++}else {r--}}return false}

復雜度分析

時間復雜度：O(sqrt?)。最壞情況下 l 和 r 一共枚舉了 0 到 sqrt?
里的所有整數。

空間復雜度：O(1)。