(13)Go查找表求四数相加

1)暴力解法：时间复杂度O(n^4)

2)将A中元素放入查找表：
时间复杂度：O(n^3)，空间复杂度O(n)

3)将A,B中元素放入查找表
时间复杂度：O(n^2)，空间复杂度O(n^2)

方法3实现：时间复杂度O(n^2)+O(n^2) = O(n^2)
func fourSumCount(A []int, B []int, C []int, D []int) int {
    m := make(map[int]int)

    // 时间复杂度O(n^2),不同的元素有可能得到相同的值,val为该值出现的次数
    for _, v1 := range A {
        for _, v2 := range B {
            m[v1+v2]++
        }
    }

    count := 0
    // 时间复杂度O(n^2)
    for _, v1 := range C {
        for _, v2 := range D {
            index := 0 - v1 - v2
            if m[index] > 0 {
                count += m[index]
            }
        }
    }
    return count
}

提交leetcode，通过