数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时装学
法律研究4Sum II 以 Python 编写
假设我们有四个包含整数值的列表 A、B、C、D，我们需要计算出有多少个元组 (i, j, k, l) 能使 A[i] + B[j] + C[k] + D[l] 为零。考虑所有 A、B、C、D 具有相同的长度 N，其中 0 ≤ N ≤ 500。请记住所有整数都在 -228 至 228 - 1 的范围内，并且结果必定小于 231 - 1。因此，如果输入为 A = [1, 2]、B = [-2, -1]、C = [-1, 2]、D = [0, 2]，则输出将为 2。这是因为有两个元组，分别是 (0, 0, 0, 1)，其中 A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0，另一个元组是 (1, 1, 0, 0)，其中 A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
为解决此问题，我们将按照以下步骤进行操作 -
- 构建一个名为 sums 的映射
- 对于 A 中的每个元素 i
- 对于 B 中的每个元素 j
- 如果 sums 映射中不存在 i + j，则设置 sums[i + j] := 1
- 否则增加 sums[i + j] 的值
- 对于 B 中的每个元素 j
- counter := 0
- 对于 C 中的每个元素 i
- 对于 D 中的每个元素 j
- 如果 sums 中存在 (-1)*(i + j)，则 counter := counter + sums[-1 * (i + j)]
- 对于 D 中的每个元素 j
- 返回 counter
示例
我们来看看以下实现，以便更好地理解 -
class Solution(object):
def fourSumCount(self, A, B, C, D):
sums ={}
for i in A:
for j in B:
if i+j not in sums:
sums[i+j] = 1
else:
sums[i+j] +=1
counter = 0
for i in C:
for j in D:
if -1 * (i+j) in sums:
#print(-1 * (i+j))
counter+=sums[-1*(i+j)]
return counter
ob1 = Solution()
print(ob1.fourSumCount([1,2], [-2,-1], [-1,2], [0,2]))输入
[1,2] [-2,-1] [-1,2] [0,2]
输出
2
更新于: 2020 年 4 月 28 日
679 次浏览
广告