629. Pairs Across Two Sorted Lists
Two non-decreasing lists are given, along with a target. Count the pairs of POSITIONS
(i, j) with a[i] + b[j] = target, taking one value from each list.
Positions are counted, so repeated values give repeated pairs.
1 2 3 and 2 3 4, target 5 -> 3 (1,4) (2,3) (3,2)
1 1 and 1 1, target 2 -> 4 every position pairs with every position
## Converging from opposite ends of DIFFERENT lists
One pointer starts at the front of a, the other at the BACK of b:
i = 0, j = m-1
while i < n and j >= 0:
s = a[i] + b[j]
s < target -> i += 1
s > target -> j -= 1
s == target -> count the equal runs on both sides
The argument is the 605 one, applied across two lists. If the sum is too small, a[i] paired
with anything still available in b is also too small, because b[j] is the largest of what
remains. So a[i] is finished.
## The equal case is where this differs from 605
When a[i] + b[j] = target, you cannot simply record one pair and step both pointers, because
there may be MANY equal values on each side and every combination is a valid pair.
Count the run of values equal to a[i], call it ca, and the run equal to b[j], call it
cb. All ca * cb combinations sum to the target, so add the product and skip both runs
entirely:
va = a[i]; ca = 0
while i < n and a[i] == va: ca += 1; i += 1
vb = b[j]; cb = 0
while j >= 0 and b[j] == vb: cb += 1; j -= 1
count += ca * cb
1 1 and 1 1 with target 2 answers 4, which is 2 * 2. Stepping one position at a time
there gives 2 and is the standard wrong answer.
## The special case that is not one
When va + vb = target and va == vb, the two runs are in DIFFERENT lists, so there is no
double counting and no need to subtract anything. That differs from the single-list version of
this problem, where a run pairing with itself needs c * (c-1) / 2.
Knowing which of the two situations you are in is the whole trap. Here the lists are separate, so the plain product is right.
## Overflow
With both lists full of the same value, the count is n * m, up to 4 * 10^10. The COUNT
needs 64 bits, and so do the sums.
## Cost
Time O(n + m). Space O(1).
Constraints - `1 ≤ n, m ≤ 200000` - `-10^9 ≤ each value and the target ≤ 10^9` - both lists are non-decreasing
Input
The first line contains three integers n, m and target.
The second line contains n integers in non-decreasing order.
The third line contains m integers in non-decreasing order.
Output
Print one integer, the number of position pairs whose values add to the target.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.