Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l)
there are such that A[i] + B[j] + C[k] + D[l]
is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l)
,使得 A[i] + B[j] + C[k] + D[l] = 0
。
为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。
例如:
输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
264ms
1 class Solution { 2 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 3 var map: [Int: Int] = [:] 4 for i in 0..<A.count { 5 for j in 0..<B.count { 6 let sum = A[i] + B[j] 7 map[sum, default: 0] += 1 8 } 9 } 10 11 var count = 0 12 for i in 0..<C.count { 13 for j in 0..<D.count { 14 let sum = C[i]+D[j] 15 if let negativeOfSum = map[-sum] { 16 count += negativeOfSum 17 } 18 } 19 } 20 21 return count 22 } 23 }
312ms
1 class Solution { 2 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 3 var map: [Int: Int] = [:] 4 for i in A.indices { 5 for j in B.indices { 6 map[A[i] + B[j], default: 0] += 1 7 } 8 } 9 10 var result = 0 11 for i in C.indices { 12 for j in D.indices { 13 result += map[-C[i]-D[j], default:0] 14 } 15 } 16 17 return result 18 } 19 }
436ms
1 class Solution { 2 func Max(_ A: ([Int], Int), _ B: ([Int], Int)) -> ([Int], Int) { 3 if A.0.count > B.0.count { 4 return A 5 }else{ 6 return B 7 } 8 } 9 func Min(_ A: ([Int], Int), _ B: ([Int], Int)) -> ([Int], Int) { 10 if A.0.count < B.0.count { 11 return A 12 }else{ 13 return B 14 } 15 } 16 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 17 var nums = [A, B, C, D] 18 let A1 = Max(Max((nums[0],0), (nums[1],1)), Max((nums[2],2), (nums[3],3))) 19 nums.remove(at: A1.1) 20 let B1 = Min(Min((nums[0],0), (nums[1],1)), (nums[2], 2)) 21 nums.remove(at: B1.1) 22 let C1 = nums[0] 23 let D1 = nums[1] 24 25 var dict = [Int:Int]() 26 for a in A1.0 { 27 for b in B1.0 { 28 if let n = dict[a + b]{ 29 dict[a + b] = n + 1 30 }else{ 31 dict[a + b] = 1 32 } 33 } 34 } 35 var count = 0 36 for c in C1 { 37 for d in D1 { 38 if let n = dict[0 - c - d] { 39 count += n 40 } 41 } 42 } 43 return count 44 } 45 }
540ms
1 class Solution { 2 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 3 var res:Int = 0 4 var n:Int = A.count 5 var m1:[Int:Int] = [Int:Int]() 6 var m2:[Int:Int] = [Int:Int]() 7 for i in 0..<n 8 { 9 for j in 0..<n 10 { 11 if m1[A[i] + B[j]] == nil 12 { 13 m1[A[i] + B[j]] = 1 14 } 15 else 16 { 17 m1[A[i] + B[j]]! += 1 18 } 19 if m2[C[i] + D[j]] == nil 20 { 21 m2[C[i] + D[j]] = 1 22 } 23 else 24 { 25 m2[C[i] + D[j]]! += 1 26 } 27 } 28 } 29 for (key,val) in m1 30 { 31 if m2[-key] != nil 32 { 33 res += val * m2[-key]! 34 } 35 } 36 return res 37 } 38 }
548ms
1 class Solution { 2 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 3 var result = 0 4 var map: [Int: Int] = [:] 5 for a in A { 6 for b in B { 7 let sum = a + b 8 if let count = map[sum] { 9 map[sum] = count + 1 10 } else { 11 map[sum] = 1 12 } 13 } 14 } 15 16 for c in C { 17 for d in D { 18 let sum = -(c + d) 19 if let count = map[sum] { 20 result += count 21 } 22 } 23 } 24 25 return result 26 } 27 }
880ms
1 class Solution { 2 func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int { 3 4 var res = 0 5 6 var CDRecord = [Int : Int]() 7 8 for c in C { 9 for d in D { 10 if let r = CDRecord[c + d] { 11 CDRecord[c + d] = r + 1 12 } else { 13 CDRecord[c + d] = 1 14 } 15 } 16 } 17 18 for a in A { 19 for b in B { 20 let complete = 0 - (a + b) 21 22 if let value = CDRecord[complete] { 23 res += value 24 } 25 } 26 } 27 return res 28 } 29 }