leetcode

4Sum II

4Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        hashtable = {}
        for a in A:
            for b in B:
                if a + b in hashtable:
                    hashtable[a + b] += 1
                else:
                    hashtable[a + b] = 1
        counter = 0
        for c in C:
            for d in D:
                if -(c + d) in hashtable:
                    counter += hashtable[-(c + d)]
        return counter

collections.Counter version

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        import collections
        AB = collections.Counter(a+b for a in A for b in B)
        return sum(AB[-c-d] for c in C for d in D)

output

1
2
3
4
5
6
7
8
In [490]: A=[1,2]
     ...: B=[-2,-1]
     ...: C=[-1,2]
     ...: D=[0,2]
     ...:
In [491]: s = Solution(); print s.fourSumCount(A, B, C, D)
2

8.3. collections — High-performance container datatypes

Python标准库——collections模块的Counter类

Python：使用Counter进行计数统计及collections模块

不可不知的Python模块: collections

leet code