“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

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 = 5Copy the code

Example 2:

Input: c = 3 Output: falseCopy the code

Example 3:

Input: c = 4 Output: trueCopy the code

Example 4:

Input: c = 2 Output: trueCopy the code

Example 5:

Input: c = 1 Output: trueCopy the code

Tip:

  • 0 <= c <= 231 - 1

A is an integer greater than or equal to 0. B is an integer greater than or equal to 0.

So the question is, if c squared and n is an integer, does that mean c is equal to n squared plus 0 squared

If n is not an integer, then 0 cannot be either a or B, so where do we go next to look for possible values?

It can only be an integer greater than 0 and less than or equal to n. Then we fix one number, get the sum of the squares of the other number to be c-a², and then take the square root of that number. If the square root of that number is an integer, then the sum of the squares of the two numbers is C

Returns false knowing that no combination was found in the above range

At this point, the solution to the problem is complete, the code is as follows:

var judgeSquareSum = function(c) { let max = Math.sqrt(c); if(isInteger(max)) return true; For (let I = 1; i<max; i++){ const target = Math.sqrt(c-Math.pow(i,2)) if(isInteger(target)) return true; } return false; Function isInteger(num){return math.floor (num) === num}};Copy the code

There is still room for improvement in the above code

If the condition is not met when I = 1, assume that the corresponding target is a non-integer close to 10, then when I is 10 later, the corresponding target must also be not an integer

The probability is a non-integer close to 1, so it is meaningless for I to go to a positive integer close to target when the target corresponding to I does not meet the condition

So we can change Max to target if target does not meet the criteria

If the optimization logic is not clear from the above description, you can leave the console comment in the code below and, given a c=1002, check the number of loops before and after Max =target.

var judgeSquareSum = function(c) { let max = Math.sqrt(c); if(isInteger(max)) return true; For (let I = 1; i<max; i++){ const target = Math.sqrt(c-Math.pow(i,2)) // console.log(i,target) if(isInteger(target)) return true; max = target; } return false; Function isInteger(num){return math.floor (num) === num}};Copy the code

At this point, we are done with leetcode-633- the sum of squares

If you have any questions or suggestions, please leave a comment!