Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Question 633 — Sum of squares

1. Title Description

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

Second, train of thought analysis

Double pointer method

A2 + b2 = c, the value range of a and b is [0, SQRT (c)]; Since B2 = c-A2, it can be seen that with the increase of A, B decreases, and the change directions of the two are opposite, so the two-pointer method is considered.

A = 0, b = math.floor (math.sqrt (c));

Calculate the value of A2 + b2;

Greater than c, the right pointer moves left;

< c, left pointer moves right;

Equal to c returns true;

If none of the above conditions is returned, the search fails, false.

JavaScript code

var judgeSquareSum = function(c) {
    let a = 0, b = Math.floor(Math.sqrt(c));
    while(a <= b) {
        if ((a*a + b*b) === c) return true;
        if((a*a + b*b) < c) a++;
        if((a*a + b*b) > c) b--;
    }
    return false;
};
Copy the code

Four,

This topic is a typical example of the use of double Pointers. The two ends move closer to the middle, and the pointer moves left or right according to the conditions that are met. Search in turn, knowing that the conditions are met or all conditions are not met, and knowing that the search fails.

Five, the last

I’m deadwood White, a programmer who loves to share. If you like this post, be sure to like it and follow ❤️