Пифагорова тройка удовлетворяет уравнению a² + b² = c². Ключевое наблюдение — работать со возведёнными в квадрат значениями напрямую, что преобразует задачу в поиск трёх чисел, где c² - b² = a² — более простую проверку равенства.
Подход состоит из двух шагов:
set для проверки совпадающих парdef has_pythagorean_triplet(arr):
squares = sorted([x**2 for x in arr])
for i in range(len(squares) - 1, 1, -1):
seen = set()
for j in range(i - 1, -1, -1):
if (squares[i] - squares[j]) in seen:
return True
seen.add(squares[j])
return False
squares[i] представляет кандидата в гипотенузу (c²)seensquares[i] - squares[j] уже есть в seen, то условие a² + b² = c² выполнено и функция возвращает TrueO(n²) — один внешний цикл по кандидатам, один внутренний цикл с поиском в setO(n) — для списка squares и сета seenFalse из-за границ циклаВозведение всех элементов массива в квадрат перед сортировкой необходимо, потому что это позволяет алгоритму использовать проверку принадлежности множеству для проверки равенства вместо необходимости применения двухуказательного подхода.
Новый — ещё не проверен сообществом
Вы