Three entries that cancel out

Scenario

A bank app records every change to an account as a signed amount in cents: a deposit is positive, and a withdrawal is negative. Entries may repeat.

An auditor looks for three entries that cancel each other out, such as a transfer that was split in two and then reversed. You are asked to count the sets of three entries whose amounts add up to zero. Two entries with equal amounts are still different entries.

Your task

Write count_zero_triples(entries).

entries is the list of signed amounts, in no particular order. Amounts may repeat.
A triple is three different positions i < j < k.
Return the number of triples with entries[i] + entries[j] + entries[k] == 0.
Count triples by position. Equal amounts at different positions give different triples.

Examples

Example 1 (traced)#

text2 lines

Input:  entries = [-2, 0, 1, 1, 2, -1]
Output: 4

Sort the entries: -2, -1, 0, 1, 1, 2. Fix the first entry, then walk two pointers over the entries after it. On a match, count the runs of equal values at each end and multiply.

First	lo value	hi value	Total	What happens
-2	-1	2	-1	too low: lo moves up
-2	0	2	0	match: runs of 1 and 1, add 1. Count is 1
-2	1	1	0	match, both ends equal: choose 2 of 2, add 1. Count is 2. Stop
-1	0	2	1	too high: hi moves down
-1	0	1	0	match: runs of 1 and 2, add 2. Count is 4

The later first entries 0, 1 and 1 have no partners that cancel them. The answer is 4.

Example 2#

text2 lines

Input:  entries = [0, 0, 0, 0]
Output: 4

Every amount is 0. Any three of the four entries cancel, so there are 4 triples.

Example 3#

text2 lines

Input:  entries = [1, 2, 3]
Output: 0

The only triple adds up to 6.

Constraints

1 ≤ entries.length ≤ 3,000 (entries in one audit window)
-100,000 ≤ entries[i] ≤ 100,000 (amounts in cents)

What does n ≤ 3,000 tell you?

Checking every triple costs about n × n × n ÷ 6 checks. At n = 3,000 that is 4.5 × 10^9: about 45 seconds at 10^8 operations a second. Sorting and then walking two pointers for each first entry costs about n × n ÷ 2 steps, 4.5 million.

The count can reach 3,000 × 2,999 × 2,998 ÷ 6, about 4.5 × 10^9. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).

Scenario

A bank app records every change to an account as a signed amount in cents: a deposit is positive, and a withdrawal is negative. Entries may repeat.

Your task

Write count_zero_triples(entries).

entries is the list of signed amounts, in no particular order. Amounts may repeat.
A triple is three different positions i < j < k.
Return the number of triples with entries[i] + entries[j] + entries[k] == 0.
Count triples by position. Equal amounts at different positions give different triples.

Examples

Example 1 (traced)#

text2 lines

Input:  entries = [-2, 0, 1, 1, 2, -1]
Output: 4

Sort the entries: -2, -1, 0, 1, 1, 2. Fix the first entry, then walk two pointers over the entries after it. On a match, count the runs of equal values at each end and multiply.

First	lo value	hi value	Total	What happens
-2	-1	2	-1	too low: lo moves up
-2	0	2	0	match: runs of 1 and 1, add 1. Count is 1
-2	1	1	0	match, both ends equal: choose 2 of 2, add 1. Count is 2. Stop
-1	0	2	1	too high: hi moves down
-1	0	1	0	match: runs of 1 and 2, add 2. Count is 4

The later first entries 0, 1 and 1 have no partners that cancel them. The answer is 4.

Example 2#

text2 lines

Input:  entries = [0, 0, 0, 0]
Output: 4

Every amount is 0. Any three of the four entries cancel, so there are 4 triples.

Example 3#

text2 lines

Input:  entries = [1, 2, 3]
Output: 0

The only triple adds up to 6.

Constraints

1 ≤ entries.length ≤ 3,000 (entries in one audit window)
-100,000 ≤ entries[i] ≤ 100,000 (amounts in cents)

What does n ≤ 3,000 tell you?

The count can reach 3,000 × 2,999 × 2,998 ÷ 6, about 4.5 × 10^9. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).