Подсчитайте триплеты из отсортированного массива, имеющего разность между соседними элементами, равную D

Опубликовано: 22 Сентября, 2022

Дан отсортированный массив arr[] , состоящий из N положительных целых чисел и целого числа D , задача состоит в том, чтобы найти количество троек (i, j, k) , таких что arr[j] – arr[i] = D и arr[k ] – arr[j] = D и 0 ≤ i < j < k < N .

Примеры:

Input: arr[] = {1, 2, 4, 5, 7, 8, 10}, D = 3
Output: 3
Explanation:
Following are the triplets having the difference between the adjacent elements is D(= 3) are:

  1. {1, 4, 7}
  2. {4, 7, 10}
  3. {2, 5, 8}

Therefore, the total count of triplets is 3.

Input: arr[] = {1, 2, 4, 5, 7, 8, 10}, D = 1
Output: 0

Наивный подход: самый простой подход к решению этой проблемы состоит в том, чтобы сгенерировать все триплеты данного массива и подсчитать те триплеты, у которых разница между соседними элементами равна D (= 3).

Временная сложность: O(N 3 )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, рассматривая каждый элемент массива как последний элемент триплета и проверяя два предыдущих элемента, т. е. (arr[i] — D) и (arr[i] — 2 * D) существует в массиве или нет. Выполните следующие действия, чтобы решить проблему.

  • Инициализируйте HashMap, скажем, M , который хранит частоту элементов массива.
  • Инициализируйте переменную, скажем , как 0 .
  • Пройдите по заданному массиву arr[] и выполните следующие шаги:
    • Увеличьте частоту arr[i] на 1 в HashMap M .
    • Теперь проверьте, присутствуют ли элементы (arr[i] — D) и (arr[i] — 2 * D) в HashMap или нет. Если установлено, что это правда , то увеличьте значение ans на freq[arr[i] – D] * freq[arr[i] – 2 * D] .
  • После выполнения вышеуказанных шагов выведите значение ans как результирующее количество триплетов в массиве.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ