923. 3Sum With Multiplicity

Link

Solution

1. record the times of each number ( 0~100)

2. calculate the possible combination

3 cases :

               1.  i == j == k
                 result shall / 6 to avoid repeated. (the combination of 3 number is 3!)
               2.  i == j && i!=k
                 result shall /2 to avoid repeated. (the combination of 2 number is 2!)
               3.  i < j && j < k

   public int threeSumMulti(int[] A, int target) {
        long[] num = new long[101];
        long ret = 0;
        for(int i = 0 ; i < A.length; i++){
            num[A[i]]++;
        }
        
        for(int i = 0; i < 101; i++){
            
            for(int j = 0; j < 101; j++){
                int k = target - i - j;
                if (k > 100 || k < 0) continue;

                if( i == j && j == k){
                    ret += num[i] * (num[i] - 1) * (num[i] - 2) / 6;
                }
                else if ((i != k && i == j)){
                    ret += num[i] * (num[i] - 1) * (num[k]) / 2;
                }             
                else if( i < j && j < k)
                    ret += num[i] * num[j] * num[k];
            }
        }
        return (int)(ret % (1e9 + 7));
    }