Pairs With a Given Sum — Solution & Editorial
Sweep once with a frequency map of earlier elements: each x pairs with the earlier count of K − x.
Complexity: O(N)
Watch out: The pair count can be ~N2/2 ≈ 5×109 — return it in 64 bits.
Sweep once with a frequency map of earlier elements: each x pairs with the earlier count of K − x.
Complexity: O(N)
Watch out: The pair count can be ~N2/2 ≈ 5×109 — return it in 64 bits.