★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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 = [4,5,0,-2,-3,1], K = 5Output: 7Explanation: 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. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 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. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 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 += v10             x %= K11             if x < 012             {13                 x += K14             }15             f[x] += 116         }17         var ret:Int = 018         for i in  0..

---

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) % K11             res += prefixArr[prefix]12             prefixArr[prefix] += 113         }14         15         return res16     }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..
      
        0 {18                 subArraysCount += (count * (count - 1))/219             }20         }21 22         return subArraysCount23     }    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..

---

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 + K11             }12             13             if let value = mod[sum]{14                 result += value15                 mod[sum] = value + 116             }else{17                 mod[sum] = 118             }19         }20         21         return result22     }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] += 110         }11         var res = sums[0]12         for s in sums {13             if s > 1 {14                 res += s*(s-1)/215             }16         }17         18         return res19     }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 += K11             }12             result += counts[current, default:0]13             counts[current] = counts[current, default:0] + 114         }15         return result16     }17 }