3Sum With Multiplicity LeetCode solution in C++

1
class Solution {
2
 public:
3
  int threeSumMulti(vector<int> &arr, int target) {
4
    long long ans = 0;
5
    int MOD = pow(10, 9) + 7;
6

7
    // step 1: create a counting array;
8
    vector<long long> counting(101); // create a vector with size == 101;
9

10
    for (auto &value : arr) counting[value]++; // count the number;
11

12
    // step 2: evaluate all cases: x, y, z;
13
    // case 1: x != y != z;
14
    for (int x_idx = 0; x_idx < counting.size() - 2; x_idx++) {
15
      if (counting[x_idx] < 1) continue;
16

17
      int target_tmp = target - x_idx;
18
      for (int y_idx = x_idx + 1; y_idx < counting.size() - 1; y_idx++) {
19
        if (counting[y_idx] < 1) continue;
20

21
        if (target_tmp - y_idx <= 100 && target_tmp - y_idx > y_idx) {
22
          ans += counting[x_idx] * counting[y_idx] * counting[target_tmp - y_idx];
23
          ans %= MOD;
24
        }
25
      }
26
    }
27

28
    // case 2: x == y != z;
29
    for (int x_idx = 0; x_idx < counting.size() - 1; x_idx++) {
30
      if (counting[x_idx] < 2) continue;
31

32
      int target_tmp = target - 2 * x_idx;
33
      if (target_tmp <= 100 && target_tmp > x_idx) {
34
        ans += counting[x_idx] * (counting[x_idx] - 1) / 2 * counting[target_tmp];
35
        ans %= MOD;
36
      }
37
    }
38

39
    // case 3: x != y == z;
40
    for (int x_idx = 0; x_idx < counting.size() - 1; x_idx++) {
41
      if (counting[x_idx] < 1) continue;
42

43
      int target_tmp = target - x_idx;
44
      if (target_tmp % 2 != 0) continue;
45

46
      if (target_tmp / 2 <= 100 && target_tmp / 2 > x_idx && counting[target_tmp / 2] > 1) {
47
        ans += counting[x_idx] * counting[target_tmp / 2] * (counting[target_tmp / 2] - 1) / 2;
48
        ans %= MOD;
49
      }
50
    }
51

52
    // case 4: x == y == z;
53
    for (int x_idx = 0; x_idx < counting.size(); x_idx++) {
54
      if (counting[x_idx] < 3) continue;
55

56
      if (x_idx * 3 == target) {
57
        ans += counting[x_idx] * (counting[x_idx] - 1) * (counting[x_idx] - 2) / 6;
58
        ans %= MOD;
59
      }
60
    }
61

62
    return ans;
63
  }
64
};