【前缀和】560. 和为 K 的子数组 && 974. 和可被 K 整除的子数组

 题目链接

974. 和可被 K 整除的子数组

560. 和为 K 的子数组

今天刷题的时候，刷了这两题，感觉挺有意思的。代码写起来挺简单的，但是思路和其中的细节以及涉及到的知识点确实让我挺意外的。这里写个博客解析一波，也是巩固一下。

力扣上的两道题。

代码实现：

class Solution {
    public int subarraySum(int[] nums, int k) {
      // 这里不能用双指针或者滑动窗口来优化暴力解法,因为有零和负数  
      // 这道题可以转化成 以 i 位置为结尾的所有子数组里
      // 即在 [0,i-1] 区间内有多少个前缀和等于 sum[i]-k
      
      // 前缀 + 哈希表 

      // 三个细节问题:
      // 1.前缀和加入哈希表的时机: 
      //不能一次性全部计算完前缀和然后一股脑丢进去,不然后来再来遍历找是否有子数组符合要求的时候会重复
      //所以在 i 位置的时候先计算结果 然后丢进去
      //2. 不用真的创建一个前缀和数组,用一个变量即可
      //3. 如果整个前缀和等于 k 呢,那么此时就是[0,-1]的前缀和等于0这个字符串符合
      // 所以要默认在Hash表中加一个 [0,1];                   
      Map<Integer,Integer> hashMap = new HashMap<>();
      // 前一个位置的前缀和
      int sum =0,ret=0;
      hashMap.put(0,1);
      // 对于以 i 位置为结尾的所有子数组 开始遍历
      for(int i =0;i<nums.length;i++){
         // 更新成当前位置的前缀和
         sum+=nums[i];
         //更新结果
         ret+=hashMap.getOrDefault(sum-k,0);
         // 丢进哈希表
         hashMap.put(sum,hashMap.getOrDefault(sum,0)+1);
      }
      return ret;
    }
}

 这道题和上道题其实很像，就是需要额外需要两个知识点。

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
      //额外补充两个知识点:
      //1.同余定理:若(a-b)➗p = k(商)......0 
      //  即  若(a-b) 能被 p 整除  则 a%p = b%p

      //2.c++,java:[负数%正数]的结果以及修正
      // 负 % 正 = 负 --修正正负统一-- 即 a(整数包括负数) % b(整数)  =  (a%p+p)%p
      // 思路和细节处理 和上道题 找子数组和为 k 的个数一样.
      // 前缀和 + 哈希表
      // 将题目转化成 在[0,i-1]内 找到有多少个前缀和的余数等于 (sum%k+k)%k 的余数
      
      //表示前缀和
      int sum =0;
      int ret=0;
      Map<Integer,Integer> hash = new HashMap<>();
      // 当刚前缀和刚好可以整除 k
      hash.put(0,1); 
      for(int i=0;i<nums.length;i++){
        //更新当前位置的前缀和
        sum+=nums[i];
        //对当前 i 位置更新结果
        ret+=hash.getOrDefault((sum%k+k)%k,0);
        //把当前的前缀和丢进哈希表中
        hash.put((sum%k+k)%k,hash.getOrDefault((sum%k+k)%k,0)+1);
      }
      return ret;
    }
}