Title

給定一個整數數組 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

Solve

暴力

暴力的方法當然是最好想也是最好實現的，可惜會超時：

def subarraysDivByK_violence(self, A: List[int], K: int) -> int:ans = 0for i in range(len(A)):for j in range(i + 1, len(A) + 1):if sum(A[i:j]) % K == 0:ans += 1return ans

前綴和

一看到子數組和，馬上就得想到用“前綴和”。

先來看一下什么是前綴和：從數組第0項到當前項的總和。
如果用一個數組preSum表示：

• preSum[0]：數組A 第 0 項 到 第 0 項 的總和
• preSum[1]：數組A 第 0 項 到 第 1 項 的總和
• preSum[2]：數組A 第 0 項 到 第 2 項 的總和
• ……

于是有：$$preSum[i]=A[0]+A[1]+\dots +A[i]$$
所以有：$$A[i]=preSum[i]?preSum[i?1]$$
可推出：$$A[i]+\dots +A[j]=preSum[j]?preSum[i?1]$$
考慮邊界情況，當i=0時，i-1=-1，讓preSum[-1]=0，可得：$$A[0]+A[1]+\dots +A[j]=preSum[j]$$
這樣可以讓邊界情況也能套用通式。

題目中說的子數組的元素之和，就是數組第i項到第j項的和。

求子元素之和能被K整除的子數組數目，等價于求有幾種i，j組合，使得i~j項的和mod K == 0，即滿足$$(preSum[j]?preSum[i?1])modK==0$$等價于$$pre[j]modK==pre[i?1]modK$$

---

preSum 數組的每一項，怎么求？

• 前一項的前綴和+當前項=當前項的前綴和
• 求出preSum數組項讓它mod K，mod完看哪兩項相等，統計次數
• 通式有i,j兩個變量，找出所有相等的兩項，需要兩層循環

引入哈希表

• 不關心前綴和對應數據A的哪一項，即不關心具體位置
• 關系出現過哪些前綴和%K的結果和對應的次數
• 用一個變量preSum，保存每次求出的前綴和%K，存入哈希表
  • key:前綴和%K，數值作為key
  • value:這個結果出現了幾次

---

流程梳理

預置邊界情況：map提前放入0:1，代表前綴和mod K == 0已經出現過1次

遍歷數據A的每一項，求當前項的前綴和mod K，存入map中

• 如果之前沒有存過，則作為key存入，值為1
• 如果之前已經存過，則對應的值+1（說明存在之前求出的前綴和，它mod K==當前前綴和 mod K，將之前求出的前綴和 mod K出現的次數累加給ans）

復雜度分析

時間復雜度：O(n)
空間復雜度：O(K)

Code

def subarraysDivByK(self, A: List[int], K: int) -> int:ans, preSum, modKMap = 0, 0, {0: 1}for i in range(len(A)):preSum = (preSum + A[i]) % K# 因為負數取模還是負數，所以需要加 Kif preSum < 0:preSum += Kif modKMap.get(preSum, None):ans += modKMap[preSum]modKMap[preSum] += 1else:modKMap[preSum] = 1return ans

總結

以上是生活随笔為你收集整理的974. Subarray Sums Divisible by K的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。