leetcode(力扣) 454. 四数相加 II （优化暴力算法）

题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

简化题目

给了四个数组，没给数组取一个值，这四个值相加等于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，毕竟这道题没有去重操作，只要次数统计。

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

完整代码

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # 目标值是0
        res = 0
        hs_a = {}
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if nums1[i] + nums2[j] in hs_a:
                    hs_a[nums1[i] + nums2[j]] +=1
                else:
                    hs_a[nums1[i] + nums2[j]] =1
        for i in range(len(nums3)):
            for j in range(len(nums4)):
                if (0-nums3[i] - nums4[j]) in hs_a:
                    res+=hs_a[0-nums3[i] - nums4[j]]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16