Программа Javascript для поиска всех троек с нулевой суммой

Дан массив различных элементов. Задача состоит в том, чтобы найти в массиве триплеты, сумма которых равна нулю.

Примеры :

Input : arr[] = {0, -1, 2, -3, 1}
Output : (0 -1 1), (2 -3 1)

Explanation : The triplets with zero sum are
0 + -1 + 1 = 0 and 2 + -3 + 1 = 0  

Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -2  1
Explanation : The triplets with zero sum is
1 + -2 + 1 = 0   

Метод 1. Это простой метод, требующий O(n ³ ) времени для получения результата.

• Подход: наивный подход запускает три цикла и проверяет один за другим, равна ли сумма трех элементов нулю или нет. Если сумма трех элементов равна нулю, то выведите элементы, иначе выведите не найденные.
• Алгоритм:
  1. Запустить три вложенных цикла со счетчиком циклов i , j , k
  2. Первые циклы будут проходить от 0 до n-3, второй цикл — от i+1 до n-2, а третий цикл — от j+1 до n-1. Счетчик циклов представляет собой три элемента триплета.
  3. Проверьте, равна ли сумма элементов в i-м, j-м, k-м нулю или нет. Если да, выведите сумму, иначе продолжите.

Ниже приведена реализация вышеуказанного подхода:

Анализ сложности:

• Временная сложность: O(n ³ ).
  Поскольку требуется три вложенных цикла, временная сложность составляет O(n ³ ).
• Вспомогательное пространство: O(1).
  Поскольку дополнительное пространство не требуется, поэтому сложность пространства постоянна.

Метод 2: Второй метод использует процесс хеширования для получения результата и решается за меньшее время O(n ² ).

Подход: это включает в себя обход массива. Для каждого элемента arr[i] найдите пару с суммой «-arr[i]». Эта задача сводится к сумме пар и может быть решена за время O(n) с помощью хеширования.

Алгоритм:

1. Создайте хэш-карту для хранения пары ключ-значение.
2. Запустите вложенный цикл с двумя циклами: внешний цикл от 0 до n-2 и внутренний цикл от i+1 до n-1
3. Проверьте, присутствует ли сумма i-го и j-го элементов, умноженных на -1, в хэш-карте или нет.
4. Если элемент присутствует в хэш-карте, напечатайте триплет, иначе вставьте j-й элемент в хэш-карту.

Ниже приведена реализация вышеуказанного подхода:

Анализ сложности:

• Временная сложность: O(n ² ).
  Поскольку требуются два вложенных цикла, временная сложность составляет O(n ² ).
• Вспомогательное пространство: O(n).
  Поскольку требуется хэш-карта, сложность пространства линейна.

Метод 3: Этот метод использует сортировку для получения правильного результата и решается за время O(n ² ).

Подход: описанный выше метод требует дополнительного места. Идея основана на методе 2 этого поста. Для каждого элемента проверьте, что существует пара, сумма которых равна отрицательному значению этого элемента.

Алгоритм:

1. Отсортируйте массив в порядке возрастания.
2. Пройдите массив от начала до конца.
3. Для каждого индекса i создайте две переменные l = i + 1 и r = n – 1
4. Запустите цикл, пока l не станет меньше r, если сумма массива [i], массива [l] и массива [r] равна нулю, затем напечатайте триплет и разорвите цикл
5. Если сумма меньше нуля, увеличьте значение l, увеличивая значение l, сумма будет увеличиваться по мере сортировки массива, поэтому array[l+1] > array [l]
6. Если сумма больше нуля, то уменьшите значение r, увеличивая значение l, сумма будет уменьшаться по мере сортировки массива, поэтому array[r-1] < array [r] .

Ниже приведена реализация вышеуказанного подхода:

Анализ сложности:

• Временная сложность: O(n ² ).
  Требуются только два вложенных цикла, поэтому временная сложность составляет O(n ² ).
• Вспомогательное пространство: O(1), дополнительное пространство не требуется, поэтому временная сложность постоянна.

Пожалуйста, обратитесь к полной статье о поиске всех троек с нулевой суммой для получения более подробной информации!