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