【leetcode】923. 3Sum With Multiplicity
2024-09-01 00:24:15
题目如下:
Given an integer array
A
, and an integertarget
, return the number of tuplesi, j, k
such thati < j < k
andA[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
解题思路:虽然A.length 最大值是300,但是A[i]的值在0~100之间,说明A中有很多重复值,对A去重后length最大值也就100,所以O(n^3)的复杂度完全可以接受。首先对A去重,假设A[i] * A[j] * A[k] == target (i<=j<=k),那么 A[i] 、A[j]、A[k] 三者之间的值有这么几种情况:
a.三者相等: 这种情况,一共存在C(A[i]在A中的个数,3)种组合 (A[i]在A中的个数 >= 3, 这个表达的是A[i]在去重前的A出现的次数)
b.任意两者相等:假设A[i] == A[j] != A[k] ,那么一共存在 C(A[i]在A中的个数,2) * A[k]在A中出现的次数 (A[i]在A中的个数,2) >= 2)
c.三者完全不同:这个最简单,一共存在 A[i]在A中出现的次数 * A[j]在A中出现的次数 * A[k]在A中出现的次数
代码如下:
class Solution(object):
def threeSumMulti(self, A, target):
"""
:type A: List[int]
:type target: int
:rtype: int
"""
def combination(n,m):
v1 = 1
times = 0
while times < m:
v1 *= n
n -= 1
times += 1
v2 = 1
while m > 0:
v2 *= m
m -= 1
return v1 / v2 dic = {}
for i in A:
dic[i] = dic.setdefault(i, 0) + 1
ul = list(set(A))
res = 0
for i in range(len(ul)):
for j in range(i,len(ul)):
for k in range(j,len(ul)):
if (ul[i] + ul[j] + ul[k]) != target:
continue
elif ul[i] == ul[j] == ul[k]:
if dic[ul[i]] >= 3:
res += combination(dic[ul[i]],3)
elif ul[i] == ul[j]:
if dic[ul[i]] >= 2:
res += (combination(dic[ul[i]],2) * dic[ul[k]])
elif ul[i] == ul[k]:
if dic[ul[i]] >= 2:
res += (combination(dic[ul[i]], 2) * dic[ul[j]])
elif ul[j] == ul[k]:
if dic[ul[j]] >= 2:
res += (combination(dic[ul[j]], 2) * dic[ul[i]])
else:
res += (dic[ul[i]] * dic[ul[j]] * dic[ul[k]])
return res % (pow(10,9) + 7)
最新文章
- [转]Oracle存在则更新,不存在则插入
- echarts在IE8下遮挡其他组件的问题
- Struts学习总结-04 上传文件
- 第24天 runtime
- FFmpeg 官方 20160227 之后 追加 libmfx 无法在 xp 上运行的解决方法
- pom.xml中引入局域网仓库
- IIS部署WCF
- kafka管理器kafka-manager部署安装
- 【转】Linux下XenServer管理工具安装
- intel的网卡故障
- Smartclient发布的几个异常问题
- spring4.0整合mongodb3.0.4项目实践(用户验证)
- JS方式调用本地的可执行文件
- 最佳化常用测试函数 Optimization Test functions
- java文件处理工具类
- 安卓Service完全解析(上)
- Introduction of Git, Github and Gitlab
- linux下关闭网络命令
- Mycat 分片规则详解--一致性hash分片
- C语言博客作业01--分支、顺序结构
热门文章
- 51nod 1298:圆与三角形(计算几何)
- spring-boot整合mongodb多数据源的案例
- SPOJ 7258 (后缀自动机)
- vue开发微信公众号--开发准备
- POJ3233]Matrix Power Series &;&; [HDU1588]Gauss Fibonacci
- python中将&#39;12345&#39;转换为12345,不要使用int
- error C2872: ‘ofstream’ : ambiguous symbol
- nRF51822学习笔记 之 blinky_example
- 用 Flask 来写个轻博客 (30) — 使用 Flask-Admin 增强文章管理功能
- 测开之路三十一:Flask基础之请求与相应