Triples Hitting the Target

Medium

You are given an array of non-negative integers values and an integer total. Count the index triples i < j < k for which values[i] + values[j] + values[k] == total. Triples are told apart by their indices, so equal values at different positions count separately. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

values=[2, 4, 2, 4, 6], total=10 → 3

The sum 10 comes from values (2, 2, 6), with one way to pick both 2s, and (2, 4, 4), with two choices of the 2 and both 4s: 2 more ways. 3 in total.

Example 2

values=[5, 5, 5, 5, 5], total=15 → 10

Any three of the five 5s work: 5 · 4 · 3 / 6 = 10 triples.

Example 3

values=[0, 1, 2], total=4 → 0

The only triple sums to 3, not 4.

Constraints

3 ≤ len(values) ≤ 3000
0 ≤ values[i] ≤ 100
0 ≤ total ≤ 300

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Two Pointers Counting Sorting

Similar problems

Spells Without Neighbors Medium More Than a Third of the Votes Medium Most Common Values Medium A Subsequence of One Word Only Medium Pairs With a Fixed Gap Medium

Input

values=[2, 4, 2, 4, 6], total=10

Expected

Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.