[Swift]LeetCode974. 和可被 K 整除的子数组 | Subarray Sums Divisible by K
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10262262.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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] <= 100002 <= 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] <= 100002 <= 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 }