import "sort"
func fourSumCount(A []int, B []int, C []int, D []int) int {
length := len(A)
if length < 1{
return 0
}
groupA, groupB, groupC, groupD := NewGroup(A), NewGroup(B), NewGroup(C), NewGroup(D)
timesOfSum := make(map[int]int)
for _, nodeA := range groupA{
for _, nodeB := range groupB{
sumOfAB := nodeA.Val + nodeB.Val
addTimes := nodeA.Times * nodeB.Times
times, existed := timesOfSum[sumOfAB]
if existed{
times += addTimes
}else{
times = addTimes
}
timesOfSum[sumOfAB] = times
}
}
total := 0
for _, nodeC := range groupC{
for _, nodeD := range groupD{
sumOfCD := nodeC.Val + nodeD.Val
addTimes := nodeC.Times * nodeD.Times
times, existed := timesOfSum[-sumOfCD]
if existed{
total += times*addTimes
}
}
}
return total
}
type GroupNode struct{
Val int
Times int
}
func NewGroup(arr []int) []GroupNode{
sort.Ints(arr)
lastVal := arr[0]-1
nodes := make([]GroupNode, 0)
size := -1
for _, val := range arr{
if val != lastVal{
nodes = append(nodes, GroupNode{
Val: val,
Times: 0,
})
size++
lastVal = val
}
nodes[size].Times++
}
return nodes
}
作者：lonverce
链接：https://leetcode-cn.com/problems/4sum-ii/solution/zhuan-huan-cheng-liang-shu-qiu-he-by-lonverce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
