Leetcode 633. Sum of Square Numbers

문제

Given a non-negative integer c, decide whether there're two integers a and b such that a^2 + b^2 = c.

음의 값을 가지지 않는 정수 c가 주어질때 $a^2 + b^2 = c$ 가 되는 음이아닌 정수 a와 b가 있는지 여부를 리턴하시오.

예시

입력 : 5
출력 : True
이유 : 1 * 1 + 2 * 2 = 5 이다.

제한

• $0 <= c <= 2^{31} - 1$

풀이법

• 먼저 a와 b는 반드시 c의 제곱근보다 작을수 밖에 없다.
• 이 안에서 범위를 먼저 잡을수 있다.
• 그 후 왼쪽 끝과 오른쪽 끝의 가능한 값에서 two pointer 를 만들고
• 이들을 결과에 따라 이동해 탐색한다.

class Solution:
    def judgeSquareSum(self, c: int) -> bool:

		# 초기 포인터 두개
        l, r = 0, int(c ** 0.5)

        while l <= r:
        	# 계산 값
            v = l * l + r * r
            # 동일하면 있다.
            if v == c:
                return True
            # 계산값이 너무 작으면 낮은 값을 끌어올린다.
            elif v < c:
                l += 1
            # 계산값이 너무 크면 큰값을 끌어 내린다.
            else:
                r -= 1

        return False