Количество троек, которые можно удалить без изменения Среднее значение заданного массива

Учитывая массив arr[] , задача состоит в том, чтобы вычислить количество возможных триплетов, чтобы их можно было удалить из массива без изменения среднего арифметического массива.

Пример:

Input: arr[] = {8, 7, 4, 6, 3, 0, 7}
Output: 3
Explanation: The given array has 3 possible triplets such that removing them will not affect the arithmetic mean of the array. There are {7, 3, 0}, {4, 6, 0} and {3, 0, 7}.

Input: arr[] = {5, 5, 5, 5}
Output: 4 

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

• Перебрать заданный массив arr[] для всех возможных значений пар (a, b) и вставить их сумму в карту.
• При переборе массива проверьте, существует ли уже на карте ( TargetSum – (a + b) ). Если да, то увеличьте значение требуемого счетчика на его частоту.

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

Выход:

4 

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