0923._3Sum_With_Multiplicity.md

923. 3Sum With Multiplicity

难度: Medium

刷题内容

原题连接

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

内容描述

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:

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

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

直接 3sum 走起，so easy，7分钟 bug free

class Solution(object):
    def threeSumMulti(self, A, target):
        """
        :type A: List[int]
        :type target: int
        :rtype: int
        """
        def threeSum(nums, target):
            n, res = len(nums), []
            nums.sort()
            for i in range(n):
                if i > 0 and nums[i] == nums[i-1]:   # 因为i=0这个元素会直接往下执行
                    continue
                l, r = i+1, n-1
                while l < r:
                    tmp = nums[i] + nums[l] + nums[r]
                    if tmp == target:
                        res.append([nums[i], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]: 
                            l += 1
                        while l < r and nums[r] == nums[r+1]: 
                            r -= 1
                    elif tmp > target:
                        r -= 1
                    else:
                        l += 1
            return res
        # 这个函数是为了算每一种排列的情况实际上有多少种，例如(2, 2, 4) occurs 2 times;
        def cal(i, j, k, d): 
            if i == j == k:
                return d[i] * (d[i]-1) * (d[i]-2) // 6
            if i == j:
                return d[k] * d[i] * (d[i]-1) // 2 
            if i == k:
                return d[j] * d[i] * (d[i]-1) // 2
            if j == k:
                return d[i] * d[j] * (d[j]-1) // 2 
            return d[i] * d[j] * d[k]
        
        if not A or len(A) == 0:
            return 0
        d = collections.Counter(A)
        res, M = 0, 10**9 + 7
        keys = [i for i in d.keys()]
        for permu in threeSum(A, target):
            res += cal(permu[0], permu[1], permu[2], d)
            res %= M
        return res % M

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

改进一下空间，顺便缩短代码

class Solution(object):
    def threeSumMulti(self, A, target):
        """
        :type A: List[int]
        :type target: int
        :rtype: int
        """
        if not A or len(A) == 0:
            return 0
        res, n, M = 0, len(A), 10**9 + 7
        A.sort() # 先排序利于后面的相等情况处理
        
        for i in range(n):
            l, r = i+1, n-1
            while l < r:
                if A[i] + A[l] + A[r] == target:
                    if A[l] != A[r]:
                        left, right = 1, 1
                        
                        while l + 1 < r and A[l] == A[l+1]:
                            left, l = left + 1, l + 1
                        while r - 1 > l and A[r] == A[r-1]:
                            right, r = right + 1, r - 1
                            
                        res += left * right
                        res %= M
                        l, r = l + 1, r - 1
                    else:
                        res += (r-l+1) * (r-l) // 2 # 例如[2,4,4]的取法
                        res %= M
                        break
                elif A[i] + A[l] + A[r] > target:
                    r -= 1
                else:
                    l += 1

        return res % M