659. Counting Triples of Positions That Hit a Target
Given n integers and a target, count the triples of POSITIONS i < j < k whose values add to
the target exactly.
Positions are counted, so repeated values give repeated triples.
1 1 2 2 3 3 4 4 5 5, target 8 -> 20
1 1 2 2 2 2, target 5 -> 12
0 0 0, target 0 -> 1
0 0 0 0, target 0 -> 4
## Not problem 606
606 collapses duplicates and counts distinct VALUE triples. This counts positions, so
0 0 0 0 answers 4 here and 1 there.
Sorting is still allowed, because reordering does not change which MULTISETS of three values exist, and the count of position triples depends only on how many copies of each value there are.
## Fix one, then count runs
Sort. For each i, sweep lo and hi looking for target - a[i]. The non-matching moves
are the usual ones. The matching move is where the counting happens, and there are two cases.
CASE A, a[lo] != a[hi]. Count the run of values equal to a[lo], call it p, and the run
equal to a[hi], call it q. Every one of the p * q combinations sums correctly, so add the
product and skip both runs.
CASE B, a[lo] == a[hi]. Then the whole stretch from lo to hi is one value, and any TWO of
them work. With m = hi - lo + 1 positions that is m * (m-1) / 2 pairs, and the sweep for
this i is finished.
Forgetting case B double counts, because the run-product formula would multiply the same run by itself.
## Why the outer index needs no run handling
i walks every position once, and each triple is counted at its SMALLEST position exactly
once. So repeated values of a[i] are simply visited repeatedly, which is correct: they really
do start different triples.
That is the opposite of 606, where the outer index skips repeats to avoid producing the same value triple twice. Which behaviour you want follows from what is being counted, and the two problems sit next to each other to make that visible.
## Overflow
With n = 3000 all equal and a matching target, the answer is C(3000, 3), about
4.5 * 10^9. The COUNT needs 64 bits, and m * (m-1) / 2 can reach 4.5 * 10^6 on its own.
## Boundaries
Fewer than three values gives 0. All zeros with target 0 gives C(n, 3).
## Cost
Time O(n^2). Space O(1) beyond the input.
Constraints - `0 ≤ n ≤ 3000` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ target ≤ 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers. It is absent when n is 0.
Output
Print one integer, the number of position triples 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.