题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个整数数组 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 种情况。

提示：

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

解答

还记得这道题的简化版本吗？我们来计算一下两数之和的多种可能性。

如果列表中的数字都是不同的，那么我们可以很方便的使用双指针法来解决，注意一下排序的重要性：

class Solution:
    def twoSumMulti(self, A, target):
        A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:
            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                cur_ans += 1
        return cur_ans

问题就出在重复元素上面。我们在循环中，遇到左右指针对应元素之和等于目标值的情况，不能仅仅将可能性加一，而有必要考虑一下左右指针对应元素可能重复多次的情况。在这种情况下：

如果左右指针对应元素不一样，这就好办了，统计一下各自出现的次数，排列一下，也就是次数相乘即可。

但是如果左右指针对应元素一致，这就不是排列的问题，而是组合的问题，例如从n个a中选出两个组成2a，有多少种方法，不过数学知识告诉我们，答案是n*(n-1)//2。

写成代码，就是下面，读者可以自行比较一下与上面的区别。

class Solution:
    def twoSumMulti(self, A, target):
        A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:

            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                if A[left] != A[right]:
                    num_left = num_right = 1
                    while A[left] == A[left + 1]:
                        num_left += 1
                        left += 1
                    while A[right] == A[right - 1]:
                        num_right += 1
                        right -= 1
                    cur_ans += num_left * num_right
                    left += 1
                    right -= 1
                else:
                    cur_ans += (right - left + 1) * (right - left) // 2
                    break
        return cur_ans

解决了两数之和的问题，三数之和就算解决了，因为我们只需要多一层循环的嵌套即可，方便的将三数问题降维成两数问题。取出一个数，求剩余数组的两数之和可能性。

class Solution:

    def threeSumMulti(self, A, target):
        ans = 0
        A.sort()
        for i, ai in enumerate(A):
            ans += self.twoSumMulti(A[i+1:], target - ai)
        return ans % (10**9 + 7)

    def twoSumMulti(self, A, target):
        # A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:

            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                if A[left] != A[right]:
                    num_left = num_right = 1
                    while A[left] == A[left + 1]:
                        num_left += 1
                        left += 1
                    while A[right] == A[right - 1]:
                        num_right += 1
                        right -= 1
                    cur_ans += num_left * num_right
                    left += 1
                    right -= 1
                else:
                    cur_ans += (right - left + 1) * (right - left) // 2
                    break
        return cur_ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析