题目描述

简化题目

给了四个数组,没给数组取一个值,这四个值相加等于0,问能有多少种取法。

思路分析

这道题其实可以直接暴力四重for循环,只不过那样的话时间复杂度直接崩了 On四次方。

优化一下暴力算法,改成2个双重for循环,这样时间复杂度就是On²了。
思路其实也比较简单,假设从四个数组里取出来的数是a,b,c,d,就先两重for循环取a和b,然后计算a+b的值再存起来。后面再循环c和d的值,找到a+b+c+d=0即可。

细节:
1.因为题目要求仅返回满足要求的四元组就行了,所以在前面两重for循环的时候,将a+b的结果存成哈希表,也就是说 key是a+b的结果,该结果出现的次数为val。

2.在后面的两重for循环里,可以设置规则为寻找0-(c+d)的结果是否在哈希表里, 0-(c+d)=a+b 就是a+b+c+d=0嘛。

3.在统计次数的时候不是count++,而是count+ 找到结果的对应val,毕竟这道题没有去重操作,只要次数统计。

这道题不容易想到的点就在建立那个哈希表了,随便找个数组模拟一边也就能相同了。

完整代码

classSolution:deffourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int])->int:# 目标值是0
        res =0
        hs_a ={}for i inrange(len(nums1)):for j inrange(len(nums2)):if nums1[i]+ nums2[j]in hs_a:
                    hs_a[nums1[i]+ nums2[j]]+=1else:
                    hs_a[nums1[i]+ nums2[j]]=1for i inrange(len(nums3)):for j inrange(len(nums4)):if(0-nums3[i]- nums4[j])in hs_a:
                    res+=hs_a[0-nums3[i]- nums4[j]]return res
09-22 20:15