博客

题目描述

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：





提示：

解题思路

本题要求解出全部

总和可以被K整除

的子串，我们可以用前缀和在解决此问题，设

P[i]

表示数组A中前

i

个元素的前缀和，

P[i] = A[0] + A[1]+...+A[ i ]

，则

sum(i, j) = P[j] - P[i - 1]

。

sum(i, j)

可以被K整除，则

P[j] % K == P[i - 1] % K

。因此我们可以构建一个hash表，当前的

P[i]

作为key值，若可以在hash表中找到

P[i]

，则将

hash[P[i]]

中的值加到最终答案中。

注：

hash[0] = 1;

防止

A[0]

可被K整除。

完整代码

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
      int len = A.size();     
      int sum = 0; //前缀和初始化为0
      int answer = 0; //最后的答案
      unordered_map<int,int>hash; //定义hash表，根据前缀和映射到hash表中
      hash[0] = 1; //模为0时初始化为1

      for(int i = 0;i<len;i++){
        sum += A[i]; //计算前缀和
        int mod = (sum % K + K) % K; //计算取模后的值，这里还要处理负数
        if(hash.find(mod) != hash.end()){
          answer += hash[mod];
        }
        // 每次计算完当前前缀和后，在hash表中更新value值
        hash[mod]++;
      }
      return answer;
    }
};

相关内容

STL基本模板库unordered_map哈希表基本操作