923. 3Sum With Multiplicity

Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:

  1. 3 <= A.length <= 3000
  2. 0 <= A[i] <= 100
  3. 0 <= target <= 300

这道题是之前那道 3Sum 的拓展,之前那道题是说没有重复数字,而这道题却有大量的重复数字,所以每个组合可能会大量重复出现,让我们统计出所有组合的总出现次数,并对一个超大数取余。这样难度就比之前提升了不少,但是本质还是类似,都是使用双指针来解题。因为有很多重复的数字,所以将相同的数字放在一起便于统计,可以对数组进行排序,然后遍历数组,先确定一个数字 A[i],则只需要找另外两个数字,使得其和为 sum = target-A[i]。然后使用两个指针j和k分别初始化为 i+1 和 n-1,若 A[j]+A[k] 小于 sum,则将j自增1;若 A[j]+A[k] 大于 sum,则将k自减1;若 A[j]+A[k] 正好等于 sum,则此时需要统计重复数字的个数,假设跟 A[j] 相同的数字有 left 个,跟 A[k] 相同的数字有 right 个。若 A[j] 不等于 A[k],那么直接用 left 乘以 right 就是出现次数了,但如果 A[j] 等于 A[k],则相当于在 left+right 中选两个数字的不同选法,就是初高中的排列组合的知识了。完事之后j要加上 left,k要减去 right,最终别忘了 res 要对超大数取余,参见代码如下:
解法一:

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        long res = 0, n = A.size(), M = 1e9 + 7;
        sort(A.begin(), A.end());
        for (int i = 0; i < n - 2; ++i) {
            int sum = target - A[i];
            int j = i + 1, k = n - 1;
            while (j < k) {
                if (A[j] + A[k] < sum) {
                    ++j;
                } else if (A[j] + A[k] > sum) {
                    --k;
                } else {
                    int left = 1, right = 1;
                    while (j + left < k && A[j + left] == A[j]) ++left;
                    while (j + left <= k - right && A[k - right] == A[k]) ++right;
                    res += A[j] == A[k] ? (k - j + 1) * (k - j) / 2 : left * right;
                    j += left;
                    k -= right;
                }
            }
        }
        return res % M;
    }
};

我们也可以换一种思路来解题,首先使用一个 HashMap 统计出每一个数字和其出现次数之间的映射,注意这里次数最好设定为长整型 long,因为之后做乘法的时候有可能会超过整型最大值,然后遍历 HashMap 中所有的任意的两个数字组合i和j,则第三个数字k可由 target-i-j 计算得到,若k不在 HashMap 中,则说明该组合不存在,直接跳过。若 i,j,k 三个数字相等,相当于在 numCnt[i] 中任选3个数字的方法,还是排列组合的知识;若i和j相等,但不等于k,则是在 numCnt[i] 中任选2个数字的方法个数再乘以 numCnt[k];若三个数字都不相同,则直接用这三个数字 numCnt[i],numCnt[j],numCnt[k] 相乘即可,最终别忘了 res 要对超大数取余,参见代码如下:
解法二:

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        long res = 0, M = 1e9 + 7;
        unordered_map<int, long> numCnt;
        for (int num : A) ++numCnt[num];
        for (auto a : numCnt) {
            for (auto b : numCnt) {
                int i = a.first, j = b.first, k = target - i - j;
                if (!numCnt.count(k)) continue;
                if (i == j && j == k) {
                    res += numCnt[i] * (numCnt[i] - 1) * (numCnt[i] - 2) / 6;  
                } else if (i == j && j != k) {
                    res += numCnt[i] * (numCnt[i] - 1) / 2 * numCnt[k];
                } else if (i < j && j < k) {
                    res += numCnt[i] * numCnt[j] * numCnt[k];
                }
            }
        }
        return res % M;
    }
};

接下来看一种更加简洁的解法,还是使用一个 HashMap 建立数字跟其出现次数之间的映射,但是这里并不是建立原数组每个数字跟其出现次数之间的映射,而是建立数组中任意两个数字之和的出现次数的映射,该数字之和出现了几次,就说明有多少个不同的两个数组合。那么此时遍历每个数字 A[i],将 numCnt[target-A[i]] 加入结果中,因为和为 target-A[i] 的每个双数组合跟 A[i] 一起都可以组成符合题意的三数组合。此时由于新加入了数字 A[i],还要从0遍历到i,将每个数字加上 A[i] 形成新的双数组合,将其和的映射值加1,这种思路真是碉堡了,参见代码如下:
解法三:

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        int res = 0, n = A.size(), M = 1e9 + 7;
        unordered_map<int, int> numCnt;
        for (int i = 0; i < n; ++i) {
            res = (res + numCnt[target - A[i]]) % M;
            for (int j = 0; j < i; ++j) {
                int sum = A[i] + A[j];
                ++numCnt[sum];
            }
        }
        return res;
    }
};

我们也可以使用动态规划 Dynmaic Programming 来解这道题,使用一个三维的 dp 数组,其中 dp[i][j][k] 表示在范围 [0, i] 内的子数组使用k个数字能组成和为j的组合个数,则 dp[n][target][3] 即为所求,将 dp[i][0][0] 初始化为1。接下来推导状态转移方程,要新加入一个数字 A[i] 的话,那么不管这个数字能否组成新的组合,之前的所有情况这里都是继承的,即 dp[i][j][k] 至少应该加上 dp[i-1][j][k],然后再来看 A[i] 是否能构成新的数字,但假如 j 是小于 A[i] 的,那么 A[i] 是无法组成和为j的三数之和的,只有当 j 大于等于 A[i] 时才有可能,那么就还应该加上 dp[i-1][j-A[i]][k-1] 的所有情况,它们可以跟 A[i] 组成和为j的三数组合(注意代码中由于i是从1开始的,所以是 A[i-1]),参见代码如下:
解法四:

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        int n = A.size(), M = 1e9 + 7;
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(target + 1, vector<int>(4)));
        for (int i = 0; i <= n; ++i) dp[i][0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= target; ++j) {
                for (int k = 1; k <= 3; ++k) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % M;
                    if (j >= A[i - 1]) {
                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - A[i - 1]][k - 1]) % M;
                    }
                }
            }
        }
        return dp[n][target][3];
    }
};

我们还可以优化一下空间复杂度,去掉i这一维度,因为i这维度只跟 i-1 相关,可以采用逐层覆盖的方法,但一定要注意的是,这样的中间两个 for 循环应该是从后往前遍历,不然会累加出错误的值,参见代码如下:
解法五:

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        int n = A.size(), M = 1e9 + 7;
        vector<vector<int>> dp(target + 1, vector<int>(4));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = target; j >= A[i - 1]; --j) {
                for (int k = 3; k >= 1; --k) {
                    dp[j][k] = (dp[j][k] + dp[j - A[i - 1]][k - 1]) % M;
                }
            }
        }
        return dp[target][3];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/923

类似题目:

3Sum Smaller

3Sum Closest

3Sum

参考资料:

https://leetcode.com/problems/3sum-with-multiplicity/

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation