一、题目

image.png

二、分析与解答

2.1、哈希表

假设原数组的前缀和数组为 sum，且子数组 (i,j] 的区间和为 goal，那么 sum[j]-sum[i]=goal。因此我们可以枚举 j ，每次查询满足该等式的 i 的数量。
具体地，我们用哈希表记录每一种前缀和出现的次数，假设我们当前枚举到元素 nums[j]，我们只需要查询哈希表中元素sum[j]−goal 的数量即可，这些元素的数量即对应了以当前 j 值为右边界的满足条件的子数组的数量。最后这些元素的总数量即为所有和为 goal 的子数组数量。

  1. class Solution {
  2.     public int numSubarraysWithSum(int[] nums, int goal) {
  3.         int sum = 0;
  4.         HashMap<Integer,Integer> map = new HashMap<>();
  5.         int res = 0;
  6.         for (int num : nums) {
  7.             map.put(sum, map.getOrDefault(sum,0) + 1);
  8.             sum += num;
  9.             res += map.getOrDefault(sum - goal, 0);
  10.         }
  11.         return res;
  12.     }
  13. }

2.2、滑动窗口

这里左边界定义两个left1 和 left2 ，满足条件的 左边界在 [left1 , left2) 区间内。

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int left1 = 0, left2 = 0, right = 0;
        int sum1 = 0, sum2 = 0;
        int res = 0;
        while(right < n) {
            sum1 += nums[right];
            while(left1 <= right && sum1 > goal) {
                sum1 -= nums[left1];
                left1++;
            }
            sum2 += nums[right];
            while(left2 <= right && sum2 >= goal) {
                sum2 -= nums[left2];
                left2++;
            }
            res += left2 - left1;
            right++;
        }
        return res;
    }
}