923.三数之和的多种可能

链接：923.三数之和的多种可能
难度：Medium
标签：数组、哈希表、双指针、计数、排序
简介：给定一个整数数组  arr ，以及一个整数  target  作为目标值，返回满足 i < j < k 且  arr[i] + arr[j] + arr[k] == target  的元组  i, j, k  的数量。

题解 1 - cpp

• 编辑时间：2022-03-07
• 执行用时：12ms
• 内存消耗：10.6MB
• 编程语言：cpp
• 解法介绍：合并重复元素，通过双指针查找第三个数出现的次数。

class Solution {
   public:
    static const int mod = 1e9 + 7;
    // 三个数一样时， 从n个数中排列组合3个
    int comp1(int num) { return (1 + num) * num / 2; }
    // 两个数一样时， 从n个数中排列组合2个
    int comp2(int num) {
        int ans = 0;
        for (int i = 1, n = num; i <= n; i++, num--)
            ans = (ans + num * i) % mod;
        return ans;
    }
    int threeSumMulti(vector<int> &arr, int target) {
        map<int, int> m;
        for (auto &num : arr) m[num]++;
        vector<int> list;
        for (auto &item : m) list.push_back(item.first);
        int ans = 0, n = list.size();
        for (int i = 0; i < n; i++) {
            int num1 = list[i];
            for (int j = i; j < n; j++) {
                int num2 = list[j], num3 = target - num2 - num1, sum;
                if (num3 < num2) break;
                if (num1 == num2 && num1 == num3) {
                    sum = comp2(m[num1] - 2);
                } else if (num1 == num2 && num1 != num3) {
                    sum = comp1(m[num1] - 1) * m[num3];
                } else if (num1 != num2 && num2 == num3) {
                    sum = m[num1] * comp1(m[num2] - 1);
                } else {
                    sum = m[num1] * m[num2] * m[num3];
                }
                ans = (ans + sum) % mod;
            }
        }
        return ans;
    }
};