Show problems as
Classic problem #923MediumArrayHash TableTwo PointersSortingCounting

3Sum With Multiplicity

Real-world version: Weight Triples Hitting The Target
Tracked in this browser only
Read 3Sum With Multiplicity on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot belt has weighed every parcel in a batch, giving loads, where loads[i] is the weight of the parcel at position i in kilograms.

A dispatcher wants to know how many ways three parcels can be pulled off the belt so their weights add up to exactly target kilograms. Count triples of positions (i, j, k) with i < j < k and loads[i] + loads[j] + loads[k] == target. Two triples are different when the positions differ, even if the three weights are identical.

The count can be enormous, so return it modulo 1000000007.

Examples

Example 1

Input
loads = [2, 2, 5, 3, 1, 9], target = 10
Output
2

Positions (0, 2, 3) weigh 2, 5 and 3, which add to 10, and positions (1, 2, 3) weigh the same three amounts. No other choice of three positions adds to 10.

Example 2

Input
loads = [50, 50, 50, 50, 100, 0], target = 150
Output
8

Any three of the four parcels weighing 50 kg add to 150 kg, which is four triples. Taking the 0 kg parcel, the 100 kg parcel and one of the four 50 kg parcels also adds to 150 kg, which is four more.

Example 3

Input
loads = [4, 5, 6], target = 15
Output
1

There is only one choice of three positions on this belt, and 4 + 5 + 6 is 15, so it qualifies.

Constraints

  • 3 <= loads.length <= 3000
  • 0 <= loads[i] <= 100
  • 0 <= target <= 300

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_weight_triples(loads: list[int], target: int) -> int:
Java
public int countWeightTriples(int[] loads, int target)

More on the same topics