## Algorithm

Problem Name: 923. 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 `109 + 7`.

Example 1:

```Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
```

Example 2:

```Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
```

Example 3:

```Input: arr = [2,1,3], target = 6
Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.
```

Constraints:

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

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int threeSumMulti(int[] nums, int target) {
Arrays.sort(nums);
for (int i = 0; i  <  nums.length; i++) {
int updatedTarget = target - nums[i];
int startIdx = i + 1;
int endIdx = nums.length - 1;
while (startIdx  <  endIdx) {
if (nums[startIdx] + nums[endIdx] < updatedTarget) {
startIdx++;
} else if (nums[startIdx] + nums[endIdx] > updatedTarget) {
endIdx--;
} else if (nums[startIdx] != nums[endIdx]) {
int leftIdx = 1;
int rightIdx = 1;
while (startIdx + 1  <  endIdx && nums[startIdx] == nums[startIdx + 1]) {
leftIdx++;
startIdx++;
}
while (endIdx - 1 > startIdx && nums[endIdx] == nums[endIdx - 1]) {
rightIdx++;
endIdx--;
}

startIdx++;
endIdx--;
} else {
answer = (answer + ((endIdx - startIdx + 1) * (endIdx - startIdx) / 2)) % 1000000007;
break;
}
}
}
}
}
``````
Copy The Code &

Input

cmd
arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output

cmd
20

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const threeSumMulti = function(A, target) {
const d = {};
let res = 0;
const mod = Math.pow(10, 9) + 7;
for (let i = 0; i  <  A.length; i++) {
res += d[target - A[i]] >= 0 ? d[target - A[i]] : 0;
res %= mod;
for (let j = 0; j  <  i; j++) {
d[A[i] + A[j]] = (d[A[i] + A[j]] || 0) + 1;
}
}
return res % mod;
};
``````
Copy The Code &

Input

cmd
arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output

cmd
20

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def threeSumMulti(self, A, target):
c = collections.Counter(A)
res = 0
for i, j in itertools.combinations_with_replacement(c, 2):
k = target - i - j
if i == j == k: res += c[i] * (c[i] - 1) * (c[i] - 2) // 6
elif i == j != k: res += c[i] * (c[i] - 1) // 2 * c[k]
elif k > i and k > j: res += c[i] * c[j] * c[k]
return res % (10**9 + 7)
``````
Copy The Code &

Input

cmd
arr = [1,1,2,2,2,2], target = 5

Output

cmd
12