Подсчитайте триплеты из массива, такого что a[j] – a[i] ≤ a[k] – a[j] ≤ 2 * (a[j] – a[i])

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

Примеры:

Input: arr[] = {5, 3, 12, 9, 6}
Output: 4
Explanation: All triplets satisfying the conditions are {3, 5, 9}, {3, 6, 9}, {3, 6, 12}, {6, 9, 12}

Input: arr[] = {1, 2, 3}
Output: 1

Наивный подход: самый простой подход — сгенерировать все возможные триплеты и для каждого из них проверить, удовлетворяет ли он заданным условиям или нет.

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

Эффективный подход. Описанный выше подход можно оптимизировать с помощью бинарного поиска. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив arr[] .
• Инициализируйте переменную, скажем , как 0, чтобы сохранить количество троек.
• Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
  • Выполните итерацию в диапазоне [i+1, N], используя переменную j , и выполните следующие шаги:
    • Инициализируйте X как arr[j] – arr[i] .
    • Найдите нижнюю границу arr[j]+X с помощью lower_bound и сохраните ее индекс в переменной l .
    • Точно так же найдите верхнюю границу arr[j] + 2×X , используя функцию по умолчанию upper_bound, и сохраните ее индекс в переменной r .
    • Добавьте rl к переменной ans .
• После выполнения вышеуказанных шагов выведите ans в качестве ответа.

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

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