Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumprefix-sum

Binary Subarrays With Sum

Problem (restated)

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

Intuition

Classic prefix-count: for each prefix S, add count of prefixes equal to S-goal.

Approaches

Prefix sum hash

Tested only

Time O(n)Space O(n)

Idea. Map prefix→count; initialize prefix 0 with count 1; accumulate answers.

Walkthrough. [1,0,1,0,1], goal=2 → 4 subarrays.

Trade-offs. Sliding window atMost(goal)-atMost(goal-1) also works for binary arrays.

Solution

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

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

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?