aboutsummaryrefslogtreecommitdiff
path: root/3sum_multiplicity.cpp
blob: 66f1f2c02ca1d05d6eea076de1cec9f56012646c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
  int threeSumMulti(vector<int> &arr, int target) {
    int n = arr.size(), mod = 1e9 + 7, ans = 0;
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
      ans = (ans + m[target - arr[i]]) % mod;
      for (int j = 0; j < i; j++)
        m[arr[i] + arr[j]]++;
    }
    return ans;
  }
};

int main() {}