930.和相同的二元子数组

链接：930.和相同的二元子数组
难度：Medium
标签：数组、哈希表、前缀和、滑动窗口
简介：给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。

题解 1 - typescript

• 编辑时间：2021-07-08
• 执行用时：1800ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：遍历两次。

function numSubarraysWithSum(nums: number[], goal: number): number {
  const len = nums.length;
  const sums = [0];
  for (let i = 0; i < len; i++) sums.push(nums[i] + sums[sums.length - 1]);
  let ans = 0;
  for (let i = 1; i <= len; i++) {
    for (let j = 0; j < i; j++) {
      const num = sums[i] - sums[j];
      if (num < goal) break;
      if (num === goal) ans++;
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-07-08
• 执行用时：92ms
• 内存消耗：45.6MB
• 编程语言：typescript
• 解法介绍：利用哈希表储存前缀和进行快速遍历。

function numSubarraysWithSum(nums: number[], goal: number): number {
  let ans = 0;
  let sum = 0;
  const map = new Map<number, number>();
  for (const num of nums) {
    map.set(sum, (map.get(sum) ?? 0) + 1);
    sum += num;
    ans += map.get(sum - goal) ?? 0;
  }
  return ans;
}