# 923. 3Sum With Multiplicity

### Description

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`.

### Constraints

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/3sum-with-multiplicity/)
* ProgramCreek
* [YouTube](https://youtu.be/jZcAldZP1ag)

### **Examples**

{% tabs %}
{% tab title="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.
{% endtab %}

{% tab title="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.
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}
```java
/**
 * Time complexity : 
 * Space complexity : 
 */

// Time Limit Exceeded

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        int n = arr.length;
        long result = 0;
        Arrays.sort(arr);
        
        for(int i = 0; i < n-2; i++) {
            int t = target - arr[i];
            int left = i + 1, right = n-1;
            while(left < right) {
                int sum = arr[left] + arr[right];
                if(sum < t) {
                    left++;
                } else if(sum  > t) {
                    right--;
                } else {
                    int tempRight = right;
                    while(left < right && arr[left] + arr[right] == t) {
                        result++;
                        right--;
                    }
                    right = tempRight;
                    left++;
                }
            }
        }
        return (int) (result%1000000007);
    }
}
```
{% endtab %}

{% tab title="Solution 2" %}
```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private final int MOD = 1000000007;
    
    public int threeSumMulti(int[] arr, int target) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap();
        
        for(int i = 0; i < arr.length; i++) {
            result = (result + map.getOrDefault(target-arr[i], 0)) % MOD;
            
            for(int j = 0; j < i; j++) {
                map.put(arr[i]+arr[j], map.getOrDefault(arr[i]+arr[j], 0) + 1);
            }
        }

        return result;
    }
}
```
{% endtab %}

{% tab title="Solution 3" %}
```java
/**
 * Time complexity : O(N^2), where N is the length of array.
 * Space complexity : O(N)
 */

class Solution {
    private final int MOD = 1000000007;
    
    public int threeSumMulti(int[] arr, int target) {
        int result = 0;
        for(int i = 0; i < arr.length; i++) {
            int[] count = new int[101];
            for(int j = i+1; j < arr.length; j++) {
                int k = target - arr[i] - arr[j];
                if(k >= 0 && k <= 100 && count[k] > 0) {
                    result = (result + count[k]) % MOD;
                }
                count[arr[j]]++;
            }
        }
        return result;
    }
}
```
{% endtab %}

{% tab title="Solution 4" %}
```java
/**
 * Time complexity : O(N + 100*100) => O(N)
 * Space complexity : O(100) => O(1)
 */
 
 class Solution {
    private final int MOD = 1_000_000_007;
    
    public int threeSumMulti(int[] arr, int target) {
        long result = 0;
        long[] count = new long[101];
        
        for(int val: arr) {
            count[val]++;
        }
        
        for(int i = 0; i <= 100; i++) {
            for(int j = i; j <= 100; j++) {
                int k = target - i - j;
                if(k < 0 || k > 100) {
                    continue;
                }
                if(i == j && j == k) {
                    result += (count[i] * (count[i]-1) * (count[i]-2) / 6);
                } else if(i == j && j != k) {
                    result += ((count[i] * (count[i]-1)/2) * count[k]);
                } else if(i < j && j < k) {
                    result += (count[i] * count[j] * count[k]);
                }
            }
        }
        return (int) (result%MOD);
    }
}
```
{% endtab %}
{% endtabs %}

### **Follow up**

*
