LeetCode 923 - 3Sum With Multiplicity

https://leetcode.com/problems/3sum-with-multiplicity/

Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[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: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[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.

Note:

1. 3 <= A.length <= 3000
2. 0 <= A[i] <= 100
3. 0 <= target <= 300

X. Map store pair sum
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution

    public int threeSumMulti(int[] A, int target) {
        Map<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++) {
                int temp = A[i] + A[j];
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
        return res;
    }




public int threeSumMulti(int[] A, int target) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int n = A.length;
        long result = 0;
        
        for(int i = 0; i + 1 < n; i++){
            for(int j = i + 1; j < n; j++){
                if(count.containsKey(target - A[i] - A[j])){
                    result += 1L * count.get(target - A[i] - A[j]); 
                    //System.out.println(result);
                }
            }
            count.put(A[i], count.getOrDefault(A[i], 0) + 1);
        }
        
       // System.out.println(result);
        return (int) (result%(1000000000 + 7));
    }

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Long> map = new HashMap<>();
        for (int a : A) {
            map.put(a, map.getOrDefault(a, 0l) + 1);
        }
        long result = 0;
        int M = (int)1e9 + 7;
        for (int a : map.keySet()) {
            for (int b : map.keySet()) {
                if (b < a || a == b && map.get(a) == 1) {
                    continue;
                }
                int c = target - a - b;
                if (c < b || !map.containsKey(c)) {
                    continue;
                }
                if (a == b && b == c) {
                    if (map.get(a) == 2) {
                        continue;
                    }
                    result += nCk(map.get(a), 3);
                } else if (a == b) {
                    result += nCk(map.get(a), 2) * map.get(c);
                } else if (b == c) {
                    if (map.get(b) == 1) {
                        continue;
                    }
                    result += nCk(map.get(b), 2) * map.get(a);
                } else {
                    result += (map.get(a) * map.get(b) * map.get(c));
                }
                result %= M;
            }
        }
        return (int)result;
    }
    private long nCk(long n, int k) {
        if (k == 3) {
            return (n * (n - 1) * (n - 2)) / 6;
        } else {
            return n * (n - 1) / 2;
        }
    }




https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)

Count the occurrence of each number.
using hashmap or array up to you.

Loop i on all numbers,
loop j on all numbers,
check if k = target - i - j is valid.

Add the number of this combination to result.
3 cases covers all possible combination:

1. i == j == k
2. i == j != k
3. i < k && j < k

Time Complexity:
3 <= A.length <= 3000, so N = 3000
But 0 <= A[i] <= 100
So my solution is O(N + 101 * 101)

    public int threeSumMulti(int[] A, int target) {
        long[] c = new long[101];
        for (int a : A) c[a]++;
        long res = 0;
        for (int i = 0; i <= 100; i++)
            for (int j = i; j <= 100; j++) {
                int k = target - i - j;
                if (k > 100 || k < 0) continue;
                if (i == j && j == k)
                    res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
                else if (i == j && j != k)
                    res += c[i] * (c[i] - 1) / 2 * c[k];
                else if (j < k)
                    res += c[i] * c[j] * c[k];
            }
        return (int)(res % (1e9 + 7));
    }

X. 3 pointers
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.

while (j + l < k && A[j + l] == A[j]) { ++l; } 
while (j < k - r && A[k - r] == A[k]) { ++r; }

solving the duplicated cases is quite impressive, that is the solution I am looking for

    private static final int  m = 1_000_000_007;
    public int threeSumMulti(int[] A, int target) {
        Arrays.sort(A);
        int res = 0;
        for (int i = 0; i < A.length - 2; ++i) {
            int j = i + 1;
            int k = A.length - 1;
            while (j < k) {
                if (A[j] + A[k] < target - A[i]) { ++j; }
                else if (A[j] + A[k] > target - A[i]) { --k; }
                else {
                    if (A[j] == A[k]) {
                        // If A[j...k] are all equal, then there are C(k - j + 1, 2) 
                        // combinations that meet the requirement.
                        res = (res + (k - j + 1) * (k - j) / 2) % m;
                        break;
                    }
                    int l = 1, r = 1;
                    while (j + l < k && A[j + l] == A[j]) { ++l; } // l: number of elements equal to A[j].
                    while (j < k - r && A[k - r] == A[k]) { ++r; } // r: number of elements equal to A[k].
                    res = (res + l * r) % m; // found l * r cases that meet the requirement.
                    j += l; // forward j by l steps.
                    k -= r; // backward k by r steps.
                }
            }
        }
        return res;
    }

X. DP
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

dp[i][j][k] represents number of combinations using k numbers within A[0] ... A[i] with the sum of j.
Then dp[n][target][3] is the result. O(n * target)

    public int threeSumMulti(int[] A, int target) {
        int n = A.length, M = (int)1e9 + 7;
        int[][][] dp = new int[n + 1][target + 1][4];
        for (int i = 0; i <= n; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int k = 1; k <= 3; k++) {
                    dp[i + 1][j][k] = dp[i][j][k];
                    dp[i + 1][j][k] %= M;
                    if (j >= A[i]) {
                        dp[i + 1][j][k] += dp[i][j - A[i]][k - 1];
                        dp[i + 1][j][k] %= M;
                    }
                }
            }
        }
        return dp[n][target][3];
    }




X. https://zxi.mytechroad.com/blog/math/leetcode-923-3sum-with-multiplicity/

Time complexity: O(n + |target|^2)

Space complexity: O(|target|)

https://my.oschina.net/yysue/blog/2250875

# step1 统计数组中每个元素出现的次数
一个元素I出现的次数记为count(I)

# step2 分类
记：I=A[i], J=A[j], K=A[k], C(count(I),3) 表示从count(I)个数中取3个的组合数
I=J=K     C(count(I), 3)
I=J!=K    C(count(I), 2) * count(K)
I!=J=K    count(I) * C(count(K), 2)
I!=J!=K   count(I) * count(J) * count(K)

# 复杂度
Time complexity: O(n + target^2)
Space complexity: O(100)

下面是参考视频中的截图，其中的i,j,k是数而不是index

public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007; // 因为最大数为10^9+7

    // 计算数组中不同元素出现的个数   因为 0 <= A[i] <=100
    long[] c = new long[101]; // 定义成long，在计算中不用转换
    for (int a : A) c[a]++;

    long ans = 0;
    for (int i = 0; i <= target; i++) {
        for (int j = i; j <= target; j++) {
            int k = target - i - j;
            if (k < 0 || k >= c.length || k < j) continue;
            if (c[i] == 0 || c[j] == 0 || c[k] == 0) continue;
            if (i ==j && j == k) {
                ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6;
            } else if (i ==j && j != k) {
                ans += c[i] * (c[i] - 1) / 2 * c[k];
            } else if (i != j && j == k) {
                ans += c[i] * (c[j] - 1) * c[j] / 2;
            } else {
                ans += c[i] * c[j] * c[k];
            }
            ans %= MOD;
        }
    }
    return (int)ans;
}

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    long ans = 0;

    Arrays.sort(A);

    for (int i = 0; i < A.length; ++i) {

      // We'll try to find the number of i < j < k

      // with A[j] + A[k] == T, where T = target - A[i].

      // The below is a "two sum with multiplicity".

      int T = target - A[i];

      int j = i + 1, k = A.length - 1;

      while (j < k) {

        // These steps proceed as in a typical two-sum.

        if (A[j] + A[k] < T)

          j++;

        else if (A[j] + A[k] > T)

          k--;

        else if (A[j] != A[k]) { // We have A[j] + A[k] == T.

          // Let's count "left": the number of A[j] == A[j+1] == A[j+2] == ...

          // And similarly for "right".

          int left = 1, right = 1;

          while (j + 1 < k && A[j] == A[j + 1]) {

            left++;

            j++;

          }

          while (k - 1 > j && A[k] == A[k - 1]) {

            right++;

            k--;

          }

          ans += left * right;

          ans %= MOD;

          j++;

          k--;

        } else {

          // M = k - j + 1

          // We contributed M * (M-1) / 2 pairs.

          ans += (k - j + 1) * (k - j) / 2;

          ans %= MOD;

          break;

        }

      }

    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    long[] count = new long[101];

    for (int x : A)

      count[x]++;

    long ans = 0;

    // All different

    for (int x = 0; x <= 100; ++x)

      for (int y = x + 1; y <= 100; ++y) {

        int z = target - x - y;

        if (y < z && z <= 100) {

          ans += count[x] * count[y] * count[z];

          ans %= MOD;

        }

      }

    // x == y != z

    for (int x = 0; x <= 100; ++x) {

      int z = target - 2 * x;

      if (x < z && z <= 100) {

        ans += count[x] * (count[x] - 1) / 2 * count[z];

        ans %= MOD;

      }

    }

    // x != y == z

    for (int x = 0; x <= 100; ++x) {

      if (target % 2 == x % 2) {

        int y = (target - x) / 2;

        if (x < y && y <= 100) {

          ans += count[x] * count[y] * (count[y] - 1) / 2;

          ans %= MOD;

        }

      }

    }

    // x == y == z

    if (target % 3 == 0) {

      int x = target / 3;

      if (0 <= x && x <= 100) {

        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;

        ans %= MOD;

      }

    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    // Initializing as long saves us the trouble of

    // managing count[x] * count[y] * count[z] overflowing later.

    long[] count = new long[101];

    int uniq = 0;

    for (int x : A) {

      count[x]++;

      if (count[x] == 1)

        uniq++;

    }

    int[] keys = new int[uniq];

    int t = 0;

    for (int i = 0; i <= 100; ++i)

      if (count[i] > 0)

        keys[t++] = i;

    long ans = 0;

    // Now, let's do a 3sum on "keys", for i <= j <= k.

    // We will use count to add the correct contribution to ans.

    for (int i = 0; i < keys.length; ++i) {

      int x = keys[i];

      int T = target - x;

      int j = i, k = keys.length - 1;

      while (j <= k) {

        int y = keys[j], z = keys[k];

        if (y + z < T) {

          j++;

        } else if (y + z > T) {

          k--;

        } else { // # x+y+z == T, now calc the size of the contribution

          if (i < j && j < k) {

            ans += count[x] * count[y] * count[z];

          } else if (i == j && j < k) {

            ans += count[x] * (count[x] - 1) / 2 * count[z];

          } else if (i < j && j == k) {

            ans += count[x] * count[y] * (count[y] - 1) / 2;

          } else { // i == j == k

            ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;

          }

          ans %= MOD;

          j++;

          k--;

        }

      }

    }

    return (int) ans;

  }