923. 3Sum With Multiplicity

Version #1 Count the occurrence of all elements

Combination
Cnk = n!/(n-k)!*k!

75.68 %
class Solution {
    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Long> map = new HashMap<>();
        for (int a : A) {
            map.put(a, 1l + map.getOrDefault(a, 0l));
        }
        int mod = (int)(1e9 + 7);
        List<Integer> array = new ArrayList<>(map.keySet());
        Collections.sort(array);
        long result = 0;
        for (int i = 0; i < array.size(); i++) {
            for (int j = 0; j <= i; j++) {
                int a = array.get(j);
                int b = array.get(i);
                int c = target - a - b;
                if (c >= b && map.containsKey(c)) {
                    long countA = map.get(a);
                    long temp = 0;
                    if (a == b && b == c) {
                        temp = countA * (countA - 1) * (countA - 2) / 6;
                    } else if (a == b) {
                        long countC = map.get(c);
                        temp = countA * (countA - 1) / 2 * countC;
                    } else if (b == c) {
                        long countC = map.get(c);
                        temp = countA * countC * (countC - 1) / 2;
                    } else if (a < b && b < c) {
                        temp = countA * map.get(c) * map.get(b);
                    }
                    result = (result + temp) % mod;
                }
            }
        }
        return (int)(result % mod);
    }
}



Version #2 HashMap

16.59 %
class Solution {
    public int threeSumMulti(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        // key-sum of two, value-count
        Map<Integer, Integer> map = new HashMap<>();
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result = (result + map.getOrDefault(target - A[i], 0)) % (int)(1e9 + 7);
            for (int j = i - 1; j >= 0; j--) {
                map.put(A[i] + A[j], 1 + map.getOrDefault(A[i] + A[j], 0));
            }
        }
        return result;
    }
}