LeetCode 454. 四数相加 II

发布时间 2023-05-07 20:23:52作者: 小星code

题目链接:LeetCode 454. 四数相加 II

题意:

给定四个数组,找出在四个数组中,各取一个数,使得四个数相加和为0

解题思路:

本题给出的是四个独立的数组,只要找到nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0就可以,不用考虑有重复的四个元素相加等于0的情况,

本题解题步骤:

  1. 首先定义 一个map,key放nums1和nums2两数之和,value 放nums1和nums2两数之和出现的次数。

  2. 遍历大nums1和大nums2数组,统计两个数组元素之和,和出现的次数,放到map中。

  3. 定义int变量res用来统计 nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0 出现的次数。

  4. 在遍历大nums3和大nums4数组,找到如果 0-(nums3+nums4) 在map中出现过的话,就用res把map中key对应的value也就是出现次数统计出来。

  5. 最后返回统计值 res就可以了

完整代码如下:

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    m := make(map[int]int)   //key:a+b的数值,value:a+b数值出现的次数
    res := 0
     // 遍历nums1和nums2数组,统计两个数组元素之和,和出现的次数,放到map中
    for _, v1 := range nums1 {  
        for _, v2 := range nums2 {
            m[v1+v2]++
        }
    }
    // 遍历nums3和nums4数组,找到如果 0-(c+d) 在map中出现过的话,就把map中key对应的value也就是出现次数统计出来
    for _, v3 := range nums3 {
        for _, v4 := range nums4 {
            if _,ok :=m[-(v3+v4)];ok{//依次枚举 v3+v4,看是否存在 -(v3+v4),存在的话就加入结果res中
                  res += m[-(v3+v4)]  //因为 v3+v4 的结果可能会出现很多个的相同的结果,
                                    //因此这里是 res += m[-(v3+v4)]  而不是res++
            }
        }
    }
    return res
}