Arrays, Hashing, Two Pointers and Sliding Windows

Most array questions have an obvious $O(n^2)$ answer: check every pair. The first upgrade to try is a hash map, which stores values you have already passed so each later lookup costs $O(1)$ on average. You trade $O(n)$ memory for a factor of $n$ in time.

The standard move is the complement lookup. To count pairs of order sizes that add to a target $T$, walk the array once. At each value $x$, ask how many earlier values equal $T - x$, then record $x$.

from collections import Counter

def count_pairs(xs, target):
    seen = Counter()
    count = 0
    for x in xs:
        count += seen[target - x]
        seen[x] += 1
    return count

count_pairs([3, 5, 2, 5, 3, 7, 1], 8)  # 5

The two 3s and two 5s give $2 \times 2 = 4$ pairs, and $7 + 1$ gives one more, so the answer is 5. Looking up before inserting matters: it stops a value from pairing with itself when $T = 2x$, and it counts duplicates correctly. Time is $O(n)$, space $O(n)$.

The same idea covers a long list of interview staples. Anagram grouping keys a dictionary on "".join(sorted(word)) or on a letter count. "First repeated trade ID" is a set membership test. Whenever the inner loop of your brute force is searching for a specific value, a hash map can usually replace that loop.