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

Arnab Chakraborty

更新于: 2020年10月7日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习