1. 題目

給定一個(gè)整數(shù)數(shù)組 A，返回其中元素之和可被 K 整除的（連續(xù)、非空）子數(shù)組的數(shù)目。

示例： 輸入：A = [4,5,0,-2,-3,1], K = 5 輸出：7 解釋： 有 7 個(gè)子數(shù)組滿足其元素之和可被 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

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 類似題目：
  LeetCode 523. 連續(xù)的子數(shù)組和（求余 哈希）
  LeetCode 560. 和為K的子數(shù)組（前綴和差分）
  LeetCode 862. 和至少為 K 的最短子數(shù)組（前綴和+deque單調(diào)棧）

class Solution { public:int subarraysDivByK(vector<int>& A, int K) {unordered_map<int,int> m;//和，出現(xiàn)次數(shù)m[0] = 1;//0出現(xiàn)1次int count = 0, sum = 0;for(int i = 0; i < A.size(); ++i){// sum += A[i]+10000*K;//+10000*K，防止負(fù)數(shù)sum += (A[i]%K+K)%K;//更專業(yè)的寫(xiě)法，效果同上sum %= K;//除余sum在 0-K-1之間count += m[sum];//前面 0 - K-1的狀態(tài)有多少個(gè)，之間的連續(xù)和可被K整除m[sum]++;}return count;} };

120 ms 30.6 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 974. 和可被 K 整除的子数组（哈希map）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。