Есть ли способ решить проблему 4Sum быстрее, чем за O (n ^ 3)? - PullRequest
0 голосов
/ 08 сентября 2018

Проблема: Учитывая массив из n целых чисел и целочисленную цель, существуют ли элементы a, b, c и d в таких числах, что a + b + c + d = target? Найти все уникальные четверки в массиве, который дает сумму цели.

Итак, существует очевидное решение n ^ 3 с сортировкой, двумя вложенными для циклов и последующей проверкой.

Но есть ли способ сделать лучше? Обратите внимание, что это не проблема решения, просто посмотрите, существует ли решение, а вместо этого верните все уникальные четверки.

1 Ответ

0 голосов
/ 08 сентября 2018

Нет, невозможно найти все уникальные четверки более эффективным способом, чем O(n^3) сложность времени. Но если вы хотите подсчитать только число четверок вместо перечисления, это может быть возможно в O(n^2) сложности времени.

...