从零学算法560-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法560。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2文章来源地址https://www.toymoban.com/news/detail-618187.html

比较容易想到的是暴力解法（我承认我想不到）。为了不遗漏的得到每个连续子数组的和，即为了得到所有 nums 中下标范围为 i~j 的区间的和（0<i<=j<nums.length ），直接双重遍历即可。

  public int subarraySum(int[] nums, int k) {
      int count = 0;
      // i 为起点，遍历 j 时得到以 i 为起点的每个连续子数组的和
      // i 遍历了整个数组也就是说每个点作为起点的连续子数组都试过了，所以没有遗漏的情况
      // 比如 nums 为 [1,2,3]
      // sum 尝试了 1,1+2,1+2+3
      // 然后尝试了 2,2+3
      // 最后尝试了 3（我还是不理解我为什么想不到暴力解法）
      for (int i = 0; i < nums.length; i++) {
          int sum = 0;
          for (int j = i; j< nums.length; j++) {
              sum += nums[j];
              if (sum == k) {
                  count++;
              }
          }
      }
      return count;
  }

使用前缀和+哈希表优化，前缀和的思想其实早就学过。比如数列前两项的和 S2 为 n1+n2，前四项的和 S4 为 n1+n2+n3+n4，如果问你 n3+n4 为多少，你可以发现就是 S4-S2，即 ni+…nj = Si-S(j-1)。
前缀和就是用一个数组 s，s[n] 保存了数组 nums 前 n-1 位的和，比如 nums 为 [1,2,3]，s[3] 保存了 nums 的前两位的和即为 1+2=3。如果让你求 s[4] 你只需要 s[3] + nums[2] 即可。插一嘴得到前缀和数组的公式：

  int[] s = new int[nums.length+1];
  // 正常来说应该是 s[i] = s[i-1] + nums[i] 
  // 但是数组下标从 0 开始
  for(int i=0;i<nums.length;i++){
  	s[i+1] = s[i]+nums[i]
  }

首先再解读一下题目，题目要求可以理解为 ni+…+nj = k ，这样的 i 和 j 有几对？。而暴力解法的短处在于，先遍历 i 视为当前 i 已确定，此时再加一重遍历，视为 j 也确定，然后遍历 j 时就能不断得到 ni+..+nj, ni+...+n(j+1)...，然后统计遍历过程中有几个和等于 k 即可。但是现在有了前缀和数组，就当做数列和 S 好了，你会发现，既然我们要求 ni+…+nj，那么遍历前缀和数组时，其实就相当于确定了 j，也就是说此时我们得到的是 Sj，而 k = ni+..+nj = Sj - S(i-1) 也就是说只要存在 S(i-1) = Sj - k，那么这样的 i 有几个就表示 ni+…+nj = k 这样的 i 和 j 有几对，或者说当 j 确定时，也就是 Sj 确定时，等于 Sj - k 的前缀和有几个就表示 ni+…+nj = k 这样的 i 和 j 有几对。（比如当前前缀和为 5，k 为 2，那 5 前面有几个前缀和等于 3 就表示我能得到几个 2 了，反证一下，比如 n1+n2+n3+n4 = 5, n1+n2 = 3，那么就有 n3+n4 这样的连续和为 2）为了记录某个前缀和有几对，我们自然很容易想到用哈希表。

  public int subarraySum(int[] nums, int k) {
      if (nums.length == 0) {
          return 0;
      }
      // key:前缀和,value:出现次数
      HashMap<Integer,Integer> map = new HashMap<>();
      //细节，这里需要预存前缀和为 0 的情况，否则会漏掉前几位就满足的情况
      // 也就是会漏掉 Sj=k ，即 n1+..+nj 恰好等于 k 的情况
      // 因为这样的 n1+..+nj 虽然等于 k 但是没有 S0 给你减，那么我们就默认 n0=0,S0=0，
      // 减个 0 就不会对你的结果有任何影响了，所以需要map.put(0,1),垫下底
      map.put(0, 1);
      int count = 0;
      int presum = 0;
      // 既然是不断确定 Sj 然后往前找有几个对应的 S(i-1)，那么没必要先求出前缀和数组再遍历
      // 更新 presum 的过程实际上就是遍历前缀和数组确定 j 的过程
      for (int x : nums) {
          presum += x;
          // 当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
          // 比如 i 为 4，当前前缀和 S4 为 n1+n2+n3+n4 = presum ，如果有一个前缀和为 presum - k，
          // 比如 S2 和为 presum - k，即 n1+n2 = presum - k，那么 S4-S2 = presum - (presum - k) = k ，
          // 也就是说存在区间为 n3+n4 = k
          if (map.containsKey(presum - k)) {
              count += map.get(presum - k);//获取次数
          }
          //更新
          map.put(presum,map.getOrDefault(presum,0) + 1);
      }
      return count;
  }