Задача с собеседования в Яндекс
Дается массив 'a' длины n. Найдите количество пар i, j (1 <= i < j <= n), что a[i] + a[j]= 0.

Решение:
Давайте будем проходить по массиву слева направо зафиксировав позицию j, тогда мы должны найти количество таких i, что i < j и a[i] = -a[j]. Но если бы мы создали словарь dict и записывали бы туда количество вхождений каждого числа, когда проходились слева направо т.e dict[a[j]]++ мы бы за O(1) смоги бы находить количество i, что i < j и a[i] = -a[j]. Ровно это и сделаем.
Время работы (N)
Псевдокод в комментариях: