# 923. 3Sum With Multiplicity

###### tags: `leetcode`,`medium`

>ref: https://leetcode.com/problems/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 = 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.

>Constraints:
3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

>1. TIME:log(N+100\*100) spactial O(100)
>2. 大數乘積溢位 需要用long

    public int threeSumMulti(int[] arr, int target) {
        
        long res=0;
        
        long[] record= new long[101]; //multiple 溢位
        
        for(int a:arr){
            record[a]++;
        }
        
        for(int i=0;i<101;i++){
            
            for(int j=i;j<101;j++){
                
                int k=target-i-j;
                
                if(k<=100 && k>=0){
                    if(k==j && j==i){
                       res+= record[i]*(record[i]-1)*(record[i]-2)/6;
                    }else if(j==i && j!=k){
                        res+= record[k]*(record[i])*(record[i]-1)/2;
                    }else if(j<k){
                        res+= record[i]*(record[j])*(record[k]);
                    }
                }
                

            }
            
        }
        
        return (int)(res%(1e9 + 7));
        
        
    }

以下timeexceed limit 但可用於ksum

    int count=0;
    public int threeSumMulti(int[] arr, int target) {
        
       helper(3,arr,target,0);
        
       return count;
        
    }
    
    public void helper(int c,int[] arr,int target,int start_idx){
        
        if(c<1 || start_idx>arr.length-1) return;
        
        for(int i=start_idx;i<arr.length-c+1;i++){
            int left= target-arr[i];
            if(left>=0 && c>1){
                helper(c-1,arr,left,i+1);
            }else if(c==1 && left==0){
                count++;
            }
        }
        
        
    }