[Swift]LeetCode454.四数相加II|4SumII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10343175.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 }