454. 4Sum II

題目連結

思路

本題的輸入會給予四個陣列，並且要在四個陣列各取一個數字找到能夠讓四個數字總和為 0 的組合，最後回傳所有可能組合的數量。由於每個陣列只會取出一個數字，因此可以利用 map 來將四個陣列兩兩一組進行拆分，先將其中兩個陣列數字的加總記錄起來，再到另外兩個陣列裡尋找可能的組合，如此一來便可以找到所有可能的組合了。

在第一個雙迴圈裡面我們將 num1 + num2 的結果記錄在 map 裡面，後續在第二個雙迴圈中，由於目標是 num1 + num2 + num3 + num4 = 0，因此移動一下之後便知道 num1 + num2 = -num3 - num4，以此作為要放入檢查的 index。

Full Code

Golang

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    record := make(map[int]int)
    count := 0

    for _, num1 := range(nums1) {
        for _, num2 := range(nums2) {
            record[num1+num2]++
        }
    }

    for _, num3 := range(nums3) {
        for _, num4 := range(nums4) {
            if pairs, exists := record[-num3-num4]; exists {
                count += pairs
            }
        }
    }

    return count
}