题目分析

第一次见到这个题目是在2年前了，当初的我比现在还要菜得多，拿到题目想了10秒，4个for循环嘛~，然后TLE，随着刷的题目越来越多，时间复杂度逐渐降低。

暴力法

4个for循环，没啥好说的。

算法的**时间复杂度为$O(n^4)$，空间复杂度为$O(1)$**。用Python3的列表表达式可以简化代码，但是空间复杂度会变高，在这里就采用简化写法。

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
        """
        return len([0 for a in A for b in B for c in C for d in D if a + b + c + d == 0])

优化暴力法

第4个for循环可以改成哈希表，进行查询即可，如前3层循环得到了k，则查找D列表中-k的个数即可。这样时间复杂度可以降低一个维度。

而且遇到重复元素，可以保存在该层的哈希表中，如A中存在多个a元素，那么只需要计算第一次出现的a，当下次遍历到a时，直接查表取出数值即可。但是要注意这个哈希表是该层的，如B中存在多个b元素，那么对于每一个A中的元素，B都要重新创建该层的哈希表。

算法的**时间复杂度为$O(n^3)$，空间复杂度为$O(n)$**。

from collections import Counter


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
        """
        res = 0
        dic_d = Counter(D)
        dic_a = dict()
        for a in A:
            if a in dic_a:
                res += dic_a[a]
            else:
                dic_b = dict()
                for b in B:
                    if b in dic_b:
                        res += dic_b[b]
                    else:
                        dic_c = dict()
                        for c in C:
                            if c in dic_c:
                                res += dic_c[c]
                            else:
                                res += dic_d[-a - b - c]
        return res

分治法

这里的分治法只是意义上的将一个问题转换为两个子问题的表述。其实优化的暴力版本已经使用了分治法的思想。我们将a+b+c+d=0的问题看成了a+b+c=-d，因此将d放入哈希表中进行查找。那么如果将a+b+c+d=0看成a+b=-c-d如何呢？

我们计算a+b的值，存放在哈希表中，计算c+d的值也存放在哈希表中。那么又会减少一层循环，但是空间复杂度会高，因为不是存放d的值，而是存放c+d的值。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n^2)$**。

from collections import Counter


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
        """
        dic_ab, dic_cd = Counter([a + b for a in A for b in B]), Counter([-c - d for c in C for d in D])
        return sum([dic_ab[x] * dic_cd[x] for x in dic_ab])

刷题总结

这种题型并不难，和其他题型不同的是，其他类型的变种很复杂，可能这个题目会做，换一个题目就不会了，而该题型只要见过一次，一定会想起来如何求解。