[python]LeetCode

[python]LeetCode_633. Sum of Square Numbers

---

文章目录

• [python]LeetCode_633. Sum of Square Numbers
• 牽涉概念及時間紀錄
• 
  

  一、題目內容

• 
  

  二、想法思路

• • 1.直觀想法：
  • 2.覺得太慢了，想優化一下：
• 总结

---

牽涉概念及時間紀錄

20220409 16:15-16:24 for 第一次
與167題相似使用頭尾往中間的查找法
a**2與aa的速度比較，aa快很多

---

一、題目內容

簡而言之:

給一數字是否可以由兩個數字的平方值相加而得呢？

以下題目原文:

Given a non-negative integer c, 
decide whether there're two integers a and b such that a2 + b2 = 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

二、想法思路 1.直觀想法：

由於有167題的經驗，故在取得用來比較的上限及起點之後，
即可由兩側往中間尋找所需之值，
但由於所花時間在400ms
且只有贏過30%，故應有更好寫法
時間複雜度為O(N)
空間複雜度為O(1).

def judgeSquareSum(self, c: int) -> bool:
        sqrt_c = int(math.sqrt(c))
        start = 0
        while start <= sqrt_c:
            if start**2 + sqrt_c**2 == c:
                return True
            elif start**2 + sqrt_c**2 > c:
                sqrt_c -= 1
            else:
                start += 1
        return False

2.覺得太慢了，想優化一下：

這邊由於看了討論區大家的想法都差不多，無法理解時間差在哪裡。

後來發現使用0.5 比 math.sqrt快了一點點但由於leetcode每次上傳的結果不一，不太能當作依據。

但緊接著使用a*a 而非a2 時，速度大幅提升。

暫時沒有找到有人討論此２者的比較，
只能先暫時記錄下來。

此處的時間只有120ms
時間複雜度為O(N**0.5)
空間複雜度為O(1).

def judgeSquareSum(self, c: int) -> bool:
        sqrt_c = int(c ** 0.5)
        start = 0
        while start <= sqrt_c:
            ans= start*start + sqrt_c*sqrt_c
            if ans > c:
                sqrt_c -= 1
            elif ans < c:
                start += 1
            else:
                return True
        return False

---

总结

這題簡言之就是使用開平方根之後就由頭尾往中間尋找即可。


其中關於a**2 比a*a的速度慢很多的問題如果有大神知道的可以跟我說一下嗎？

感謝花時間看到這裡的大家。

如果有錯，請不吝告知，也可以一起討論，一起加油ＸＤ