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

 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 }

 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 }

 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 }

 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 }

 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 }

 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 }

 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 }