[Swift]LeetCode923.三数之和的多种可能|3SumWithMultiplicity

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

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

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

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

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

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

Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < kand A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: A = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

示例 1：

输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

提示：

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

80ms

 1 struct ModInt {
 2   static let MOD = 1000_000_007;
 3   
 4   var val : Int = 0
 5   
 6   init(_ v: Int) {
 7     val = v
 8   }
 9   
10   static func *(l: ModInt, r: ModInt) -> ModInt {
11     return ModInt(l.val * r.val % MOD)
12   }
13   static func *(l: ModInt, r: Int) -> ModInt {
14     return ModInt(l.val * r % MOD)
15   }
16   static func +(l: ModInt, r: ModInt) -> ModInt {
17     return ModInt(l.val + r.val % MOD)
18   }
19   static func +(l: ModInt, r: Int) -> ModInt {
20     return ModInt(l.val + r % MOD)
21   }
22   static func -(l: ModInt, r: ModInt) -> ModInt {
23     var res = l.val - r.val
24     if res < 0 {
25       res += MOD
26     }
27     return ModInt(res)
28   }
29 }
30 
31 class Solution {
32   
33   func threeSumMulti(_ A: [Int], _ target: Int) -> Int {
34     var cnt: [Int:Int] = [:]
35     for v in A {
36       if let c = cnt[v] {
37         cnt[v] = c + 1
38       } else {
39         cnt[v] = 1
40       }
41     }
42     
43     var result = ModInt(0)
44     
45     let keys = Array(cnt.keys)
46     for ai in 0..<keys.count {
47       let a = keys[ai]
48       for bi in ai..<keys.count {
49         let b = keys[bi]
50         for ci in bi..<keys.count {
51           let c = keys[ci]
52           if a+b+c == target {
53             if a == b && b == c {
54               let n = cnt[a]!
55               result = result + n*(n-1)*(n-2) / 6
56             } else if a == b {
57               let n = cnt[a]!
58               result = result + n*(n-1)*cnt[c]! / 2
59             } else if a == c {
60               let n = cnt[a]!
61               result = result + n*(n-1)*cnt[b]! / 2
62             } else if b == c {
63               let n = cnt[b]!
64               result = result + n*(n-1)*cnt[a]! / 2
65             } else {
66               result = result + cnt[a]!*cnt[b]!*cnt[c]!
67             }
68           }
69         }
70       }
71     }
72     return result.val
73   }
74 }

148ms

 1 class Solution {
 2     func threeSumMulti(_ A: [Int], _ target: Int) -> Int {
 3         guard A.count >= 3 else {
 4             return 0
 5         }
 6         let A = A.sorted()
 7         var results = [[Int]]()
 8         var dict = Dictionary( A.map { ($0, 1) }, uniquingKeysWith: +)
 9         var counter = 0
10         for i in 0...A.count - 3 {
11             if i != 0 && A[i] == A[i-1] {
12                 continue
13             }
14             var left = i + 1
15             var right = A.count - 1
16             while left < right {
17                 if left != i + 1 && A[left] == A[left - 1] {
18                     left += 1
19                     continue 
20                 }
21                 if A[i] + A[left] + A[right] == target {
22                     let temp = [A[i], A[left], A[right]]
23                     results.append(temp)
24                     left += 1
25                     right -= 1
26                 } else if A[i] + A[left] + A[right] > target {
27                     right -= 1
28                 } else  {
29                     left += 1
30                 }
31             }
32         }
33         print(results)
34         for result in results {
35             if result[0] == result[1] && result[1] == result[2] {
36                 let n = dict[result[0]]!
37                 counter += n * (n - 1) * (n - 2) / 6
38                 
39             } else if result[0] == result[1] {
40                 
41                 let n = dict[result[0]]!
42                 counter += (n * n / 2 - n / 2) * dict[result[2]]!
43     
44             } else if result[1] == result[2] {
45                 
46                 let n = dict[result[2]]!
47                 counter += (n * n / 2 - n / 2) * dict[result[0]]!
48                 
49             } else {
50                 counter += dict[result[0]]! * dict[result[1]]! * dict[result[2]]!
51                 
52             }
53         }
54         return counter % Int(1e9 + 7)
55     }
56 }

308ms

 1 class Solution {
 2     func threeSumMulti(_ A: [Int], _ target: Int) -> Int {
 3         var MOD:Int = 1_000_000_007;
 4         var ans:Int = 0;
 5         //升序
 6         var arr:[Int] = A.sorted(by: <)
 7         let len:Int = arr.count
 8         for i in 0..<len
 9         {
10             //找出i < j < k，
11             //当T = target - arr[i],arr[j] + arr[k] == T成立 .
12             var T:Int = target - arr[i]
13             var j:Int = i + 1, k:Int = len - 1
14             while(j < k)
15             {
16                 if arr[j] + arr[k] < T {j += 1}
17                 else if arr[j] + arr[k] > T {k -= 1}
18                 else if arr[j] != arr[k] 
19                 {
20                     var left:Int = 1, right:Int = 1
21                     while(j+1 < k && arr[j] == arr[j+1])
22                     {
23                         left += 1
24                         j += 1
25                     }
26                     while(k-1 > j && arr[k] == arr[k-1])
27                     {
28                         right += 1
29                         k -= 1
30                     }
31                     ans += left * right
32                     ans %= MOD
33                     j += 1
34                     k -= 1
35                 }
36                 else
37                 {
38                     ans +=  (k-j+1) * (k-j) / 2
39                     ans %= MOD
40                     break
41                 }
42             }
43         }
44         return ans
45     }
46 }

372ms

 1 class Solution {
 2     func threeSumMulti(_ A: [Int], _ target: Int) -> Int {
 3         var MOD:Int = 1_000_000_007;
 4         var ans:Int = 0;
 5         //升序
 6         var arr:[Int] = A.sorted(by: <)
 7         let len:Int = arr.count
 8         for i in 0..<len
 9         {
10             //找出i < j < k，
11             //当T = target - arr[i],arr[j] + arr[k] == T成立 .
12             var T:Int = target - arr[i]
13             var j:Int = i + 1, k:Int = len - 1
14             while(j < k)
15             {
16                 if arr[j] + arr[k] < T {j += 1}
17                 else if arr[j] + arr[k] > T {k -= 1}
18                 else if arr[j] != arr[k] 
19                 {
20                     var left:Int = 1, right:Int = 1
21                     while(j+1 < k && arr[j] == arr[j+1])
22                     {
23                         left += 1
24                         j += 1
25                     }
26                     while(k-1 > j && arr[k] == arr[k-1])
27                     {
28                         right += 1
29                         k -= 1
30                     }
31                     ans += left * right
32                     ans %= MOD
33                     j += 1
34                     k -= 1
35                 }
36                 else
37                 {
38                     ans +=  (k-j+1) * (k-j) / 2
39                     ans %= MOD
40                     break
41                 }
42             }
43         }
44         return ans
45     }
46 }