• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. 3 <= A.length <= 3000
  2. 0 <= A[i] <= 100
  3. 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 种情况。

 提示:

  1. 3 <= A.length <= 3000
  2. 0 <= A[i] <= 100
  3. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap