[Swift]LeetCode974.和可被K整除的子数组|SubarraySumsDivisiblebyK

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

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

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

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

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

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

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

368ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3         var n = A.count
 4         var f:[Int] = [Int](repeating:0,count:K)
 5         f[0] = 1
 6         var x:Int = 0 
 7         for v in A
 8         {
 9             x += v
10             x %= K
11             if x < 0
12             {
13                 x += K
14             }
15             f[x] += 1
16         }
17         var ret:Int = 0
18         for i in  0..<K
19         {
20             ret += f[i]*(f[i]-1)/2
21         }
22         return ret
23     }
24 }

372ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3      
 4         var res = 0
 5         var prefixArr = Array(repeating:0, count:K)
 6         var prefix = 0
 7         prefixArr[0] = 1
 8         
 9         for num in A {
10             prefix = (prefix + num % K + K) % K
11             res += prefixArr[prefix]
12             prefixArr[prefix] += 1
13         }
14         
15         return res
16     }
17 }

392ms

 1 class Solution {
 2     
 3     func subarraysDivByK(_ values: [Int], _ k: Int) -> Int {
 4         var reminderCount = [Int: Int]() 
 5         var sum = 0
 6 
 7         for i in 0..<values.count {
 8             sum += values[i]
 9             let reminder = (sum % k + k) % k
10             reminderCount[reminder, default: 0] += 1
11         }
12 
13         var subArraysCount = 0
14         subArraysCount += reminderCount[0] ?? 0
15 
16         for key in reminderCount.keys {
17             if let count = reminderCount[key], count > 0 {
18                 subArraysCount += (count * (count - 1))/2
19             }
20         }
21 
22         return subArraysCount
23     }    
24 }

400ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3         let N = A.count
 4         var P = [Int](repeating: 0, count: N+1)
 5         for i in 0..<N {
 6             P[i+1] = P[i] + A[i]
 7         }
 8 
 9         var count = [Int](repeating: 0, count: K)
10         for x in P {
11             count[(x%K + K)%K] = count[(x%K + K)%K] + 1
12         }
13 
14         var ans = 0;
15         for v in count {
16             ans += v*(v-1)/2
17         }
18         return ans
19     }
20 }

404ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3         var mod = [Int:Int]()
 4         var result = 0
 5         var sum = 0
 6         mod[0] = 1
 7         for num in A{
 8             sum = (sum + num)%K
 9             if sum < 0{
10                 sum = sum + K
11             }
12             
13             if let value = mod[sum]{
14                 result += value
15                 mod[sum] = value + 1
16             }else{
17                 mod[sum] = 1
18             }
19         }
20         
21         return result
22     }
23 }

408ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3         var sums: [Int] = Array(repeating: 0, count: K)
 4         var sum: Int = 0
 5         for (index, a) in A.enumerated() {
 6             sum += a
 7             sum %= K
 8             if sum < 0 { sum += K }
 9             sums[sum] += 1
10         }
11         var res = sums[0]
12         for s in sums {
13             if s > 1 {
14                 res += s*(s-1)/2
15             }
16         }
17         
18         return res
19     }
20 }

452ms

 1 class Solution {
 2     func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
 3         var counts = [0:1]
 4         
 5         var current = 0
 6         var result = 0
 7         for a in A {
 8             current = (current + a) % K
 9             while current < 0 {
10                 current += K
11             }
12             result += counts[current, default:0]
13             counts[current] = counts[current, default:0] + 1
14         }
15         return result
16     }
17 }