สมมติว่ามีรายการตัวเลขชื่อ 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 เรียงลำดับจากมากไปน้อย
- สำหรับแต่ละดัชนี i และตัวเลข n ใน tmp ทำ
- base := n
- left := i+1, right := ขนาดของ tmp -1
- while 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
