leetcode
March 14, 2024

Viiisit [LeetCode] - 930. Binary Subarrays With Sum

#php#javascript#ruby

keep learning, keep coding!

Problem - Binary Subarrays With Sum

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

翻譯蒟蒻

給定一個二進制陣列 nums 和一個整數 goal，返回具有和為 goal 的非空子數組的數量。

這裡運用前綴和的概念，描述數列中前幾項的和。使用前綴和通常可以幫助優化計算。在 dynamic programming 或陣列問題中使用，因為可以在 O(1) 的時間複雜度內計算出任意兩個位置之間的和，而不需要重新計算整個子數列的和。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
var numSubarraysWithSum = function(nums, goal) {
  let count = new Map();
  // 將前綴和為 0 的情況設置為 1
  count.set(0, 1);
  let currSum = 0;
  let totalSubarrays = 0;

  for (let num of nums) {
      currSum += num;
      // 如果 count 中存在 currSum - goal，表示存在一個子陣列的和為 goal。
      if (count.has(currSum - goal)) {
          totalSubarrays += count.get(currSum - goal);
      }
      count.set(currSum, (count.get(currSum) || 0) + 1);
  }

  return totalSubarrays;
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# @param {Integer[]} nums
# @param {Integer} goal
# @return {Integer}
def num_subarrays_with_sum(nums, goal)
  hash = Hash.new(0)
  hash[0] = 1
  sum = 0
  count = 0
  nums.each do |num|
    sum += num
    count += hash[sum - goal]
    hash[sum] += 1
  end
  count
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function numSubarraysWithSum($nums, $goal) {
  $map = [];
  $map[0] = 1;
  $sum = 0;
  $count = 0;
  for ($i = 0; $i < count($nums); $i++) {
    $sum += $nums[$i];
    if (isset($map[$sum - $goal])) {
      $count += $map[$sum - $goal];
    }
    if (isset($map[$sum])) {
      $map[$sum] += 1;
    } else {
      $map[$sum] = 1;
    }
  }
  return $count;
}

LeetCode 傳送門 - Binary Subarrays With Sum