Medium · Pair-Sum Hashing
Understand → Visualise → Practice.
Count index quadruples choosing one value from each array whose total is zero.
Count every sum a + b in a hash map. Then for every c + d, the matching first halves are exactly those with sum −(c + d).
For every x in a and y in b, increment counts[x + y].
For every z in c and w in d, add counts[−(z + w)] to the answer.
That counts all index quadruples with total 0.
O(n²) time and O(n²) space for arrays of length n.
Checking all four nested loops is O(n⁴).
Read the full guide first: Hash Maps and Hash Sets.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.