資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告