Пифагорейские тройки

Question

Кто-то задал мне вопрос (заданный ему в интервью), как найти триплеты в целочисленном массиве A [], которые удовлетворяют следующему условию:

a [i] ^ 2 + a [j] ^ 2 = a [k] ^ 2

я сделал это в o (n ^ 2 logn), можно ли это оптимизировать.

Answer 1

Вариант вашего подхода - O (n ^ 2).

def findPythagoreanTriplets(array):
  array = sorted(array)
  for i in range(len(array)):
    k = i + 2
    for j in range(i + 1, len(array)):
      while k < len(array) and (array[k] ** 2 < (array[i] ** 2 + array[j] ** 2)):
        k += 1
      if k < len(array) and (array[k] ** 2 == (array[i] ** 2 + array[j] ** 2)):
        print "%d^2 + %d^2 = %d^2" % (array[i], array[j], array[k])

Это код Python, но преобразование в C не должно быть трудным. (На самом деле этот вопрос кажется независимым от языка, поэтому я не уверен, почему у вас есть тег c ...)

Предполагается, что все входы неотрицательны. Возможно, вы могли бы заставить его работать и для отрицательных целых чисел, но вам нужно будет отсортировать их по квадрату, а не по входному значению (для неотрицательных чисел они эквивалентны).

Вместо того, чтобы выполнять бинарный поиск, вы просто выполняете линейный поиск для k, но вы можете выбрать с того места, где остановился предыдущий поиск j, поэтому поиск для k является «свободным».

Answer 2

По крайней мере, вы можете использовать хэш-таблицу для хранения квадратов.Таким образом, поиск (i ^ 2 + j ^ 2) для каждой пары будет в O (1) и в общем алгоритме займет O (n ^ 2)