923-3sum-with-multiplicity.md

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

给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

 

示例 1：

输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

 

提示：

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

---

题目标签：Two Pointers

题目链接：LeetCode / LeetCode中国

题解

该题是3Sum问题的变形。首先找不重复的三元组，然后对每个三元组看其有多少种组合方式，最后把种数累加起来即可。

Language	Runtime	Memory
python3	372 ms	N/A

class Solution:
    def twoSum(self, nums, target):
        res = []
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                if not res or res[-1][0] != nums[i]:
                    res.append([nums[i], nums[j]])
                i += 1
                j -= 1
            elif nums[i] + nums[j] > target:
                j -= 1
            else:
                i += 1
        return res

    def threeSumMulti(self, A, target):
        """
        :type A: List[int]
        :type target: int
        :rtype: int
        """
        rst = []
        A.sort()
        vt = set()
        for i, num in enumerate(A):
            if num not in vt:
                for twosum in self.twoSum(A[i+1:], target - num):
                    rst.append([num, *twosum])
                vt.add(num)
        cnt = collections.Counter(A)
        res = 0
        for muti in rst:
            t = 1
            for num in set(muti):
                if muti.count(num) == 1:
                    t *= cnt[num]
                elif muti.count(num) == 2:
                    t *= cnt[num] * (cnt[num] - 1) // 2
                else:
                    t *= cnt[num] * (cnt[num] - 1) * (cnt[num] - 2) // 6
            res += t
        return res % (10**9 + 7)