454. 4 Sum II

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