【lc刷题】923. 三数之和的多种可能(排列组合)_Day8(27/300)

27/300

难。

python里面有算排列组合的函数。这次要用到的是itertools的combinations_with_replacement()
可以对比一下combinations和combinations_with_replacement()的区别。
【lc刷题】923. 三数之和的多种可能(排列组合)_Day8(27/300)
combination = $C_{n}^{k}$ …

combinations_with_replacement(‘ABC’, 2) --> AA AB AC BB BC CC

nums = range(11)
n = 3
list = [i for i in itertools.combinations_with_replacement(nums, n) if sum(i) == 10]
print (list)
#[(0, 0, 10), (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6), (0, 5, 5), (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4), (3, 3, 4)]

【lc刷题】923. 三数之和的多种可能(排列组合)_Day8(27/300)

三数之和的多种可能
给定一个整数数组 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

这题。。感觉就是排列组合。。跟以前做的3Sum根本不一样啊，嘤嘤。。
跪了，完全懵逼，直接上大佬的，credit to @lee215，侵删。
【lc刷题】923. 三数之和的多种可能(排列组合)_Day8(27/300)

class Solution(object):

    def threeSumMulti(self, A, target):
        
        c = collections.Counter(A)#这步可以想到，得到了元素和元素个数
        #c = Counter({2: 4, 1: 2})
        res = 0
        for i, j in itertools.combinations_with_replacement(c, 2):
        
            k = target - i - j 
			'''
			A = [1,1,2,2,2,2], target = 5
			
			(i, j), k -> (1, 1), 3
			c[i],c[j],c[k]: 2,2,0
			
			(i, j), k -> (1, 2), 2
			c[i],c[j],c[k]: 2,4,4
			
			(i, j), k -> (2, 2), 1
			c[i],c[j],c[k]: 4,4,2
			'''
            
            if i == j == k: res += c[i] * (c[i] - 1) * (c[i] - 2) / 6
            #Cn(3) 譬如[0,0,0,0,0] target = 0； C5(3) = 5*4*3/6 = 10
            
            elif i == j != k: res += c[i] * (c[i] - 1) / 2 * c[k]
			#Cn(2)*Cm(1) 譬如[1,1,1,1,3] target = 5; C4(2)*C1(1)= 4*3/2*1 = 6

            elif k > i and k > j: res += c[i] * c[j] * c[k]
            #Cn(1)*Cm(1)*Cd(1) 譬如[1,1,2,2,3] target = 6；C2(1)*C2(1)*C1(1) = 4
            
        return int(res % (10**9 + 7))

唉，基础不扎实，果然要还了。。

【lc刷题】923. 三数之和的多种可能(排列组合)_Day8(27/300)

相关推荐