0454. 四数相加 II #

标签：数组、哈希表
难度：中等

题目大意 #

给定四个整数数组 nums1、nums2、nums3、nums4。计算有多少不同的（i, j, k, l）满足 nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0。

解题思路 #

直接暴力搜索的时间复杂度是 $O(n^4)$。我们可以降低一下复杂度。

将四个数组分为两组。nums1 和 nums2 分为一组，nums3 和 nums4 分为一组。

已知 $nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0$，可以得到 $nums1[i] + nums2[j] = -(nums3[k] + nums4[l])$

建立一个哈希表。两重循环遍历数组 nums1、nums2，先将 $nums[i] + nums[j]$ 的和个数记录到哈希表中，然后再用两重循环遍历数组 nums3、nums4。如果 $-(nums3[k] + nums4[l])$ 的结果出现在哈希表中，则将结果数累加到答案中。最终输出累加之后的答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        nums_dict = dict()
        for num1 in nums1:
            for num2 in nums2:
                sum = num1 + num2
                if sum in nums_dict:
                    nums_dict[sum] += 1
                else:
                    nums_dict[sum] = 1
        count = 0
        for num3 in nums3:
            for num4 in nums4:
                sum = num3 + num4
                if -sum in nums_dict:
                    count += nums_dict[-sum]

        return count