Create 923_3_sum_with_multiplicity.cpp (qiyuangong#30)

bhanu1131 · web-flow · commit 5dadae95e823 · 2020-10-31T22:26:35.000+08:00
* Create 923_3_sum_with_multiplicity.cpp, by @bhanu1131
diff --git a/cpp/923_3_sum_with_multiplicity.cpp b/cpp/923_3_sum_with_multiplicity.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+    int threeSumMulti(vector<int>& A, int target) {
+        unordered_map<int, uint64_t> count;
+        for (const auto& a : A) {
+            ++count[a];
+        }
+        uint64_t result = 0;
+        for (const auto& kvp1 : count) {
+            for (const auto& kvp2 : count) {
+                int i = kvp1.first, j = kvp2.first, k = target - i - j;
+                if (!count.count(k)) {
+                    continue;
+                }
+                if (i == j && j == k) {
+                    result += count[i] * (count[i] - 1) * (count[i] - 2) / 6;
+                } else if (i == j && j != k) {
+                    result += count[i] * (count[i] - 1) / 2 * count[k];
+                } else if (i < j && j < k) {
+                    result += count[i] * count[j] * count[k];
+                }
+            }
+        }
+        return result % static_cast<int>(1e9 + 7);
+    }
+};
