923. 3Sum With Multiplicity

// https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution
class Solution {
    public int threeSumMulti2Sum(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int mod = 1000000007;

        for (int i=0; i<A.length; i++) {
            res = (res + map.getOrDefault(target - A[i], 0))%mod;
            for (int j=0; j<i; j++) {
                map.put(A[i]+A[j], map.getOrDefault(A[i]+A[j],0)+1);
            }
        }

        return res;
    }

    // https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)
    public int threeSumMulti(int[] A, int target) {
        if (A == null || A.length < 3) {
            return 0;
        }

        HashMap<Integer, Long> map = new HashMap<>();
        long res = 0;

        for (int a : A) {
            map.put(a, map.getOrDefault(a,new Long(0))+1);
        }

        List<Integer> uniqueNums = new ArrayList<>(map.keySet());
        Collections.sort(uniqueNums);
        int n = uniqueNums.size();

        for (int i=0; i<n; i++) {
            for (int j=i; j<n; j++) {
                int n1 = uniqueNums.get(i);
                int n2 = uniqueNums.get(j);
                int n3 = target - (n1+n2);

                if (!map.containsKey(n3)) {
                    continue;
                }

                long c1 = map.get(n1);
                long c2 = map.get(n2);
                long c3 = map.get(n3);
                long add = 0;

                if (n1 == n2) {
                    if (n2 == n3) {
                        add = c1*(c1-1)*(c1-2)/6;
                    } else {
                        add = (c1*(c1-1)/2) * c3;
                    }
                } else if (n2 < n3) {
                    add = c1*c2*c3;
                }

                res += add;
            }
        }

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