923.cpp

// Problem : 923. 3Sum With Multiplicity
// Link : https://leetcode.com/problems/3sum-with-multiplicity/

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int threeSumMulti(vector<int>& arr, int X) {
        int n = arr.size(), mod = 1e9+7, ans = 0;
        unordered_map<int, int> m;

        for(int i=0; i<n; i++) {
            ans = (ans + m[X - arr[i]]) % mod;

            for(int j=0; j<i; j++)
                m[arr[i] + arr[j]]++;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> arr{1,1,2,2,3,3,4,4,5,5};
    cout << ob.threeSumMulti(arr, 8);
    return 0;
}