Given a non-negative integer c, you need to determine whether there are two integers A and b such that a2 + b2 = c.

 

Example 1:

Input: c = 5 Output: true Description: 1 * 1 + 2 * 2 = 5 Example 2:

Input: c = 3 Output: false Example 3:

Input: c = 4 Output: true Example 4:

Input: c = 2 Output: true Example 5:

Input: c = 1 Output: true

Tip:

0 <= c <= 231 – 1

Their thinking

Maintain the values of l and r,l=0,r= SQRT (c), meet the condition l<=r, when ll+rr is less than the target value, it is necessary to move the left pointer. When ll+ RR is greater than the target value, the element is too large and the right pointer needs to be moved.

The principle of

This is equivalent to fixing the right boundary one at a time, and then shrinking the left boundary. Why does the left pointer not iterate from 1 each time, but from the last left pointer? Since the condition for changing the right boundary is ll+rr>c, this proves that the sum of squares of the current two left Pointers is too large, so a smaller right pointer needs to be replaced. Why not the value before the left pointer?

For example, l-1, because L is transferred from L -1, and L -1 is transferred to L if L * L +r-r<c(note: If r is larger, the sum of squares generated by L -1 is smaller, and if r is larger, the sum of squares generated by L -1 is smaller, so you don’t need to iterate from 1, just start from the left pointer.

code

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
	

}
Copy the code

Complexity analysis

Time complexity: O(SQRT (c)). Worst-case scenario l and r together enumerate all integers from 0 to SQRT (c).

Space complexity: O(1).