Golang 四数相加 leetcode454 map哈希表

四数相加 leetcode454

本题如果直接进行四次for循环，则时间复杂度为O(N^4),超出运行时间限制。
因此我们这里使用两个分别的for循环进行遍历，则时间复杂度为O(N^2+N2).

/ 使用两遍for循环func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {index := 0record := map[int]int{}//首先对num3、nums4进行遍历，记录数据考虑到可能每组有重复数字，每遍历到一次就+1for _, i1 := range nums3 {for _, i2 := range nums4 {record[i1+i2]++}}//然后再进行nums1、nums2的遍历for _, i1 := range nums1 {for _, i2 := range nums2 {//record对应数字是几，证明能得到这个数字的组合有几个，这里就加上对应的组合数if v, ok := record[-i1-i2]; ok {index = index + v}}}return index}