Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

https://leetcode.com/problems/sum-of-square-numbers

633. Sum of Square Numbers

給定一非負整數C 請回傳是否存在a,b兩數使得a**2 + b**2 == c

Example 1:

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

Input: c = 3
Output: false


Constraints:

0 <= c <= 231 - 1


思路:
two pointer

Python Code:
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        right = math.isqrt(c)
        while right >= left:
            ans = right ** 2 + left ** 2
            if ans == c:
                return True
            elif ans < c:
                left += 1
            else:
                right -= 1

        return False


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.112.186 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718588279.A.7C6.html
推 JIWP: 把c/2，可以少跑一半
→ sustainer123: 求C平方根更小吧?
→ sixB: 太倦了
→ sustainer123: 求平方根再向下取整
→ sustainer123: 我感覺還能二分搜尋 不曉得會不會比較快
→ JIWP: c/2再取平方根
→ JIWP: 不過你有判斷式r>l，應該沒差