Chương trình kiểm tra bộ ba Pythagoras trong danh sách Python

Cho danh sách số nums, kiểm tra xem có tồn tại ba số a, b, c thỏa mãn a² + b² = c² hay không.

Ví dụ

Đầu vào: [10, 2, 8, 5, 6].
Đầu ra: True vì 8² + 6² = 64+36 = 100 = 10².

Thuật toán

1. Tạo danh sách tmp chứa bình phương các số, sắp xếp giảm dần.
2. Với mỗi chỉ mục i và giá trị n trong tmp:
   • Gán base = n.
   • Sử dụng hai con trỏ left = i+1, right = len(tmp)-1.
   • Khi left <= right:
     • Tính t = tmp[left] + tmp[right].
     • Nếu t == base, trả về True.
     • Nếu t > base, tăng left.
     • Ngược lại, giảm right.
3. Trả về False nếu không tìm thấy.

Mã nguồn Python

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]))

Đầu vào / Đầu ra

Input: [10, 2, 8, 5, 6]
Output: True