Python程式檢查給定列表中是否存在勾股數三元組

假設我們有一個名為nums的數字列表，我們需要檢查是否存在三個數字a、b和c，使得a^2 + b^2 = c^2。

因此，如果輸入類似於[10, 2, 8, 5, 6]，則輸出將為True，因為8^2 + 6^2 = 64+36 = 100 = 10^2。

為了解決這個問題，我們將遵循以下步驟：

  • tmp := nums中所有數字的平方值組成的降序列表
  • 對於tmp中的每個索引i和對應的數字n，執行以下操作：
    • base := n
    • left := i+1, right := tmp的大小 - 1
    • 當left <= right時，執行以下操作：
      • t := 將tmp[left]和tmp[right]兩個列表合併
      • 如果t等於base，則
        • 返回True
      • 否則，如果t > base，則
        • left := left + 1
      • 否則，
        • right := right - 1
  • 返回False

讓我們看看以下實現以獲得更好的理解：

示例

 即時演示

class Solution:
   def solve(self, nums):
      tmp = sorted([n*n for n in nums], reverse = True)
      for i, n in enumerate(tmp):
         base = n
         left = i+1; right = len(tmp)-1
         while left <= right:
            t = tmp[left]+tmp[right]
            if t == base:
               return True
            elif t > base:
               left += 1
            else:
               right -= 1
      return False
ob = Solution()
print(ob.solve([10, 2, 8, 5, 6]))

輸入

[10, 2, 8, 5, 6]

輸出

True

更新於: 2020年10月7日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告