文章目录

• 题目描述
• 解题思路
• 完整代码
• 相关内容

题目描述

给定一个整数数组 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哈希表基本操作