454. 4 Sum II
這一個題目的設計比較特別一點,給出四個長度一樣的陣列,要從四個陣列中挑出任意四個數字,其總和為零。
這個題目存在著暴力解,那就是四個陣列一個一個掃描,這樣的時間複雜度會是 $$O(n^4)$$ 如果說每個陣列的長度為 n
。
不過這一個題目如果用 n Sum 的思想來想的話,其實存在著另外一個解法,那就是如果我從前面兩個陣列,各挑出一個數字後,其總和如果是 k
,那我只要再另外兩個陣列,找出總和為 -k
的組合即可。
有一件事情要注意的是,從前面兩個陣列隨機挑選兩的個數字,其總和為 k
的情況其實有很多種,假設有 x
種,那後面兩個陣列每次找出總和為 -k
的情況,就可以組合出 x
種組合。
因此在計算答案時,要記得累加可以組合的情況。
這樣的方式時間複雜度可以降低到只要在 $$O(n^2) $$ 。
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
target = 0
table = defaultdict(int)
ans = 0
for num1 in nums1:
for num2 in nums2:
s = num1 + num2
table[s] = table[s] + 1
for num3 in nums3:
for num4 in nums4:
s = num3 + num4
if target - s in table:
ans += table[target-s]
return ans