给定一个整数数组 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; } };
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
