Pair Sums Shared Between Two Lists
You are given two lists, the first of n numbers and the second of m numbers. Count the ways to choose a pair of positions i < j from the first list and a pair of positions k < l from the second list so that the first list's two values add up to the same amount as the second list's two values. Print the count.
Within each list the two positions must be different, and the pair is unordered, which is what i < j and k < l express. Equal values at different positions still make different pairs.
## What most people try first
Four nested loops over the two pairs, which is about n^2 m^2 / 4. At n = m = 1000 that is roughly 2.5 * 10^11 and hopeless.
## Tabulate one list's pair sums, then scan the other's
Build a table from each achievable pair sum of the first list to HOW MANY pairs i < j produce it. That is n(n-1)/2 entries. Then for each pair k < l of the second list, add the table's count for that pair's sum.
Notice that the two lists are independent here, which is what makes this simpler than the single-list version of the same idea. A pair from the first list can never share a position with a pair from the second, so no barrier is needed and the tables can both be built up front.
## Why it is correct
A matching configuration is exactly a first-list pair and a second-list pair with the same sum. Grouping the first list's pairs by their sum and then, for each second-list pair, adding the size of the matching group, counts each configuration once: once for its own second-list pair, and within that, once for each first-list pair it matches.
## The boundary that breaks a careless implementation
Counting ordered pairs instead of unordered ones. If the inner loop runs over all j rather than j > i, every pair is seen twice and the answer comes out four times too large, since both lists are affected. Running j from i rather than i + 1 is worse: it admits the pair (i, i), which uses one position twice.
Lists shorter than two elements produce no pairs at all, so the answer is 0, and the loops must simply not execute rather than reading out of range.
## Overflow
It is the COUNT that overflows here, not the sums, and the distinction is worth getting right rather than assuming.
A pair sum reaches 2 * 10^9 in magnitude, because the values reach 10^9. The largest signed 32-bit value is 2147483647, and 2000000000 is below it, so the pair sums do in fact fit in 32 bits. Reaching for a 64-bit type for them is harmless but it is not what saves you.
The count is different. With n = m = 350 and every value 0, every first-list pair matches every second-list pair, so the answer is 350 choose 2, squared, which is 3730155625. That is above 2147483647, so the ACCUMULATOR needs 64 bits. A solution that widens the sums and leaves the counter at 32 bits fails on exactly that input and passes everything smaller.
## Cost
n^2 / 2 to build the table and m^2 / 2 lookups, about a million steps at n = m = 1000.
## Worked example
``` first = 1 2 3 second = 2 3 4
pairs of the first list: (1,2) sum 3, (1,3) sum 4, (2,3) sum 5 table: {3: 1, 4: 1, 5: 1}
pairs of the second list: (2,3) sum 5, (2,4) sum 6, (3,4) sum 7 sum 5 table has 1 adds 1 sum 6 absent adds 0 sum 7 absent adds 0
answer 1 ```
### Constraints - 1 <= n <= 1000 - 1 <= m <= 1000 - each number is between -10^9 and 10^9 - A pair sum reaches 2 * 10^9, which still fits in a signed 32-bit integer. The COUNT reaches the product of the two pair counts, which does not, so the accumulator needs a 64-bit type.