Подсчитайте триплеты из отсортированного массива, имеющего разность между соседними элементами, равную D
Дан отсортированный массив 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, 4, 7}
- {4, 7, 10}
- {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)