3Sum With Multiplicity
Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.
As the answer can be very large, return it modulo 10^9 + 7.
Example 1
Input
arr = [1,1,2,2,3,3,4,4,5,5], target = 8Output
20Enumerating by values,
(1, 2, 5) occurs 8 times, (1, 3, 4) occurs 8 times, (2, 2, 4) occurs 2 times, and (2, 3, 3) occurs 2 times, for a total of 20.Example 2
Input
arr = [1,1,2,2,2,2], target = 5Output
12Choosing one
1 from two choices and two 2s from four choices gives 2 * 6 = 12 tuples.Constraints
- 3 <= arr.length <= 3000
- 0 <= arr[i] <= 100
- 0 <= target <= 300