Description

Submission

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n = nums.size();

        unordered_map<int, vector<int>> num2maxIdx;
        for(int i = 0; i < n; ++i) {
            num2maxIdx[nums[i]].push_back(i);
        }
        
        int ret = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                for(int k = j + 1; k < n; ++k) {
                    int t = nums[i] + nums[j] + nums[k];
                    auto it = num2maxIdx.find(t);
                    if(it == num2maxIdx.end()) continue;
                    auto& v = it->second;
                    auto it2 = upper_bound(v.begin(), v.end(), k);
                    ret += v.end() - it2;
                }
            }
        }

        return ret;
    }
};