454. 4Sum II

發表於 分類於 ， 閱讀次數： 文章字數： 1k

種類 : hash table
難度 : medium
題目 : 454. 4Sum II

思維邏輯

  1. 將四個list轉為set(❌錯誤)

    1. 歷遍四個set

  2. 歷遍前兩個list，將和與次數紀錄在dict

    1. 歷遍後兩個list，若兩元素相加 * -1在dict中，count += dict[元素相加*-1]

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # 紀錄nums1, nums2 之 和, 次數
        d = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1+n2 in d:
                    d[n1+n2] += 1
                else:
                    d[n1+n2] = 1

        # 歷遍nums3, nums4, 若0 == -d, count+=d.value
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                if (n3 + n4)*-1 in d:
                    count += d[(n3 + n4)*-1]

        return count

四個list長度: n
時間複雜度: O(2n2) -> O(n2)
空間複雜度: O(2n2) -> O(n2)

難點

  1. 四個list如何有效的計算並累加次數

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
字典
dict可設定default, 省略if...else
"""
class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # 使用字典存储nums1和nums2中的元素及其和
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                # if n1 + n2 in hashmap:
                #   hashmap[n1+n2] += 1
                # else:
                #   hashmap[n1+n2] = 1
                hashmap[n1+n2] = hashmap.get(n1+n2, 0) + 1
        
        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

時間複雜度: O(n2)
空間複雜度: O(n2)