Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i &lt; j &lt; k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

&nbsp;
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.


&nbsp;
Constraints:


	3 &lt;= arr.length &lt;= 3000
	0 &lt;= arr[i] &lt;= 100
	0 &lt;= target &lt;= 300


class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        arr.sort()
        count = 0
        for i in range(0, len(arr)-2):
            rem_sum = target - arr[i]
            hash_map = {}
            for j in range(i+1, len(arr)):
                if arr[j] > rem_sum:
                    break
                if rem_sum - arr[j] in hash_map:
                    count = count + hash_map[rem_sum-arr[j]]
                # update the hash_map
                hash_map[arr[j]] = hash_map.get(arr[j], 0) + 1
        return count % 1000000007
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        long[] cnt = new long[101];
        long res = 0;
        for (int i : arr) {
            cnt[i]++;
        }
        for (int i = 0; i < 101 && i <= target; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            for (int j = i; j < 101 && i + j <= target; j++) {
                int k = target - i - j;
                if (k < j) {
                    break;
                }
                if (cnt[j] == 0 || k >= 101 || cnt[k] == 0) {
                    continue;
                }
                if (i == j && j == k) {
                    res += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 3 / 2;
                } else if (i == j) {
                    res += cnt[k] * cnt[j] * (cnt[j] - 1) / 2;
                } else if (j == k) {
                    res += cnt[i] * cnt[j] * (cnt[j] - 1) / 2;
                } else {
                    res += cnt[i] * cnt[j] * cnt[target - i - j];
                }
            }
        }
        return (int) (res % (Math.pow(10, 9) + 7));
    }
}
class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        long long ans = 0;
        int MOD = pow(10, 9) + 7;
        
        // step 1: create a counting array;
        vector<long long> counting(101); // create a vector with size == 101;
        
        for(auto &value : arr) counting[value]++; // count the number;
        
        // step 2: evaluate all cases: x, y, z;
        // case 1: x != y != z;
        for(int x_idx = 0; x_idx < counting.size() - 2; x_idx++){
            if(counting[x_idx] < 1) continue;
            
            int target_tmp = target - x_idx;
            for(int y_idx = x_idx + 1; y_idx < counting.size() - 1; y_idx++){
                if(counting[y_idx] < 1) continue;
                
                if(target_tmp - y_idx <= 100 && target_tmp - y_idx > y_idx){
                    ans += counting[x_idx] * counting[y_idx] * counting[target_tmp - y_idx];
                    ans %= MOD;
                }
            }
        }
        
        // case 2: x == y != z;
        for(int x_idx = 0; x_idx < counting.size() - 1; x_idx++){
            if(counting[x_idx] < 2) continue;
            
            int target_tmp = target - 2 * x_idx;
            if(target_tmp <= 100 && target_tmp > x_idx){
                ans += counting[x_idx] * (counting[x_idx] - 1) / 2 * counting[target_tmp];
                ans %= MOD;
            }
        }
        
        // case 3: x != y == z;
        for(int x_idx = 0; x_idx < counting.size() - 1; x_idx++){
            if(counting[x_idx] < 1) continue;
            
            int target_tmp = target - x_idx;
            if(target_tmp %2 != 0) continue;
            
            if(target_tmp/2 <= 100 && target_tmp/2 > x_idx && counting[target_tmp/2] > 1){
                ans += counting[x_idx] * counting[target_tmp/2] * (counting[target_tmp/2] - 1) / 2;
                ans %= MOD;
            }
        }
        
        // case 4: x == y == z;
        for(int x_idx = 0; x_idx < counting.size(); x_idx++){
            if(counting[x_idx] < 3) continue;
            
            if(x_idx * 3 == target){
                ans += counting[x_idx] * (counting[x_idx] - 1) * (counting[x_idx] - 2) / 6;
                ans %= MOD;
            }
        }
        
        return ans;
    }
};
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(arr, target) {
    let count=0
    arr.sort((a,b)=>a-b)
    for(let i=0;i<arr.length-2;i++){
        let j=i+1,k=arr.length-1
        while(j<k){
            let sum=arr[i]+arr[j]+arr[k]
            if(sum<target){
                j++
            }
            else if(sum>target){
                k--
            }
            else{
                if(arr[j]!==arr[k]){
                    let j1=j,k1=k
                    while(arr[j]===arr[j1]){
                        j1++
                    }
                    while(arr[k]===arr[k1]){
                        k1--
                    }
                    count+=((j1-j)*(k-k1))
                    j=j1
                    k=k1
                }
                else{
                    for(let n=1;n<=k-j;n++){
                        count+=n
                    }
                    break
                }
            }
        }
    }
    return count% (10**9 + 7)
};
3Sum With Multiplicity