目录
一·题目:
二·思路:
三·代码:
一·题目:
leetcode链接:. - 力扣(LeetCode)
二·思路:
思路:前缀和第二种表示方式即循环列出方式+同余定理+取模修正:
还是通过循环把它分为由0到i的位置一次由i位置往前走去组合,即可以得到所有的情况,因此要判断x%k=0即转化为(sum-前缀和)%k成立即可 即由同余定理——>
满足sum%k=前缀和%k 通俗一点也就是通过for循环每次遍历前缀和(sumi之前的sum)都放入了hash,当遍历到i位置,只需要判断hash中是否对应sum%k下标是否存在值即可
注意:存在负数和0,不能用滑动窗口。
三·代码:
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int sum=0,ret=0;unordered_map<int,int> hash;hash[0%k]=1;//特殊情况,这如果恰好x为此时的sumi那么对应的就是前缀和为0,即若它是,则此时hash【0】必然有数即初始化为1;for(auto a:nums){sum+=a;int remainder=(sum%k+k)%k;//这里进行了修正处理原因是如果余数出现负数,则可能会有情况不符合如:【-1,2,9】,k=2这里//2是一个子数组,但是sum加到2,此时余数是1,而hash没有对应1的下标只有-1(-1%2)故这时可以通过修正把它变为1if(hash.count(remainder)) ret+=hash[remainder];//上下顺序不能颠倒,如果颠倒则无论如何这个if肯定为真hash[remainder]++;}return ret;}
};