3Sum With Multiplicity LeetCode solution in Java

1
class Solution {
2
  public int threeSumMulti(int[] arr, int target) {
3
    long[] cnt = new long[101];
4
    long res = 0;
5
    for (int i : arr) {
6
      cnt[i]++;
7
    }
8
    for (int i = 0; i < 101 && i <= target; i++) {
9
      if (cnt[i] == 0) {
10
        continue;
11
      }
12
      for (int j = i; j < 101 && i + j <= target; j++) {
13
        int k = target - i - j;
14
        if (k < j) {
15
          break;
16
        }
17
        if (cnt[j] == 0 || k >= 101 || cnt[k] == 0) {
18
          continue;
19
        }
20
        if (i == j && j == k) {
21
          res += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 3 / 2;
22
        } else if (i == j) {
23
          res += cnt[k] * cnt[j] * (cnt[j] - 1) / 2;
24
        } else if (j == k) {
25
          res += cnt[i] * cnt[j] * (cnt[j] - 1) / 2;
26
        } else {
27
          res += cnt[i] * cnt[j] * cnt[target - i - j];
28
        }
29
      }
30
    }
31
    return (int) (res % (Math.pow(10, 9) + 7));
32
  }
33
}