Подсчитайте пары, разница между которыми и индексами различна.

Учитывая массив arr[] размера N , задача состоит в том, чтобы подсчитать все пары индексов (i, j), такие что i < j и j – i != arr[j] – arr[i] .

Примеры:

Input: arr[] = {4, 1, 3, 3}
Output: 5
Explanation:
The pair (0, 1) is a valid pair since 1 – 0 != 1 – 4.
The pair (0, 2) is a valid pair since 2 – 0 != 3 – 4, 2 != -1.
The pair (0, 3) is a valid pair since 3 – 0 != 3 – 4, 3 != -1.
The pair (1, 2) is a valid pair since 2 – 1 != 3 – 1, 1 != 2.
The pair (2, 3) is a valid pair since 3 – 2 != 3 – 3, 1 != 0.
There are a total of 5 valid pairs, so we return 5.

Input: arr = {1, 2, 3, 4, 5}
Output: 0
Explanation: There are no valid pairs.

Подход с использованием хеширования:

As per the valid pair is concerned the value of  j – i != arr[j] – arr[i], This can also be written as j – arr[j] != i – arr[i]. 

We’ll use map to keep the count of element that has value (i – arr[i]) occurred till i^th index. If we are at i^th index then the valid pair for i^th element would be just (Total number of pairs till i^th index – count of element that has value (i – arr[i]) till i^th index).

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Инициализировать карту для хранения значения (i – arr[i])
• Инициализировать результат переменной для хранения количества всех допустимых пар
• Итерация по заданному массиву
  • Сохраните количество всех предыдущих элементов, имеющих значение (i – arr[i]), в переменную count, так как это будет действовать как вся недопустимая пара с элементом с i- ^м индексом.
  • Добавьте все допустимые пары, удалив из результата недопустимые пары (т. е. результат += i – количество).
  • Увеличьте количество ( i – arr[i] ) в карте для каждого i ^-го индекса.
• Вернуть результат.

Ниже приведена реализация описанного выше подхода.

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