leetcode 923. 3Sum With Multiplicity 三数之和的多种可能

Problem: 923. 3Sum With Multiplicity 三数之和的多种可能

排序，哈希表记录每个数字的频次，双循环，拿到两个数字，最后一个数字相减得到，然后通过排列组合计算答案，需要考虑是否存在这样的情况，而且a, c不能重复的

Code

class Solution { public: const int modulo = 1e9 + 7; int threeSumMulti(vector<int>& arr, int target) { sort(arr.begin(), arr.end()); unordered_map<int, long long> ump; for(int& i : arr) { ump[i]++; } int n = arr.size(), a, c, f; unsigned long long ans = 0; for(int i = 0; i < n - 2; i++) { a = arr[i]; if(i > 0 && arr[i]==arr[i-1]) { continue; } for(int j = i + 1; j < n - 1; j++) { c = arr[j]; if(j > i + 1 && arr[j]==arr[j-1]) { continue; } f = target - a - c; if(f < c) { continue; } if(ump.count(f) != 0) { if(a == c && a == f) { if(ump[f] >= 3) { ans += ump[f] * (ump[f] - 1) * (ump[f] - 2) / 6; } else { continue; } } else if(a == c) { ans += ump[a] * (ump[a]-1) / 2 * ump[f]; } else if(c == f) { if(ump[f] >= 2) { ans += ump[f] * (ump[f] -1 ) / 2 * ump[a]; } else { continue; } } else if(a!=c && c!=f && a!=f){ ans += ump[f] * ump[a] * ump[c]; } ans %= modulo; } } } return ans; } };