930. Binary Subarrays With Sum
解題說明
題目描述
給定一個只包含 0 和 1 的二進位陣列 nums 和整數 goal，計算有多少個連續子陣列的和恰好等於 goal（即子陣列中 1 的個數恰好為 goal）。
範例：nums = [1,0,1,0,1], goal = 2
- [1,0,1] → 和=2 ✓
- [1,0,1,0] → 和=2 ✓
- [0,1,0,1] → 和=2 ✓
- [1,0,1] （後三個）→ 和=2 ✓ → 答案：4
解題思路
方案一：前綴和 + HashMap
定義前綴和 prefix[i] = nums[0] + ... + nums[i-1]（prefix[0] = 0）。
若子陣列 [i+1, j] 的和等於 goal，則：
prefix[j+1] - prefix[i] == goal
⟺ prefix[i] == prefix[j+1] - goal
對每個 j，若 HashMap 中存有 prefix[j+1] - goal 的出現次數，則加入答案。
用 count[sum] 記錄每個前綴和出現的次數（初始 count[0] = 1），遍歷時先查詢再更新。
方案二：雙滑窗（atMost 差分）
定義 atMost(k)：和 ≤ k 的子陣列個數。
exactly(goal) = atMost(goal) - atMost(goal - 1)
atMost(k) 可用滑動窗口 O(n) 計算：維護左右指標，當窗口和超過 k 時收縮左邊界；右指標每移動一步，以右指標結尾的合法子陣列有 r - l + 1 個。
特別注意：goal = 0 時，atMost(-1) 需要回傳 0（而非負數），需在 atMost 中加邊界判斷。
兩種方案時間複雜度都是 O(n)，HashMap 方案空間 O(n)，滑窗方案空間 O(1)。
C++ 解法
複雜度分析
時間複雜度
O(n)，其中 n 為陣列長度。
- HashMap 方案：一次線性遍歷，每次 HashMap 操作 O(1) 平均。
- 滑窗方案：
atMost函式被呼叫兩次，每次左右指標各只移動 O(n) 步，共 O(n)。
空間複雜度
- HashMap 方案：O(n)，HashMap 最多儲存 n+1 個不同前綴和。
- 滑窗方案：O(1)，只使用常數個額外變數，是空間最優解。
虛擬碼
Approach 1 (Prefix Sum + HashMap):
1. Initialize count = {0: 1}, sum = 0, result = 0
2. For each x in nums:
a. sum += x
b. result += count[sum - goal] (0 if not exists)
c. count[sum] += 1
3. Return result
Approach 2 (atMost trick):
atMost(nums, k):
1. If k < 0: return 0
2. left = 0, sum = 0, result = 0
3. For right from 0 to n-1:
a. sum += nums[right]
b. While sum > k: sum -= nums[left], left++
c. result += right - left + 1
4. Return result
numSubarraysWithSum(nums, goal):
1. Return atMost(nums, goal) - atMost(nums, goal - 1)其他解法
替代方案
方案一：暴力雙重迴圈
枚舉所有子陣列 [i, j]，維護滾動和並計數。
- 優點：最直觀，無需額外資料結構。
- 缺點：時間 O(n²)，n=3×10^4 時需 ~9×10^8 操作，會超時。
方案二：前綴和陣列 + 線性掃描
預先建立前綴和陣列，對每個 j，枚舉所有 i < j 查找 prefix[j] - prefix[i] == goal。
- 優點：前綴和計算簡單直觀。
- 缺點：查找仍需 O(n) 掃描，整體 O(n²)；改用 HashMap 儲存前綴和頻次才能降至 O(n)，等同方案一（HashMap 方案）。
方案三：利用陣列（固定範圍）替代 HashMap
由於 nums 只含 0 和 1，前綴和範圍為 [0, n]，可用大小 n+1 的陣列替代 HashMap。
- 優點：常數因子比 HashMap 小，實際執行更快；空間 O(n) 且快取友好。
- 缺點：僅適用於前綴和範圍有限的情況（本題可行，一般整數陣列不可行）。
延伸思考
延伸問題
-
一般整數陣列（含負數）：若
nums包含負數，滑動窗口方案無法使用（窗口和不單調），但前綴和 + HashMap 方案仍然有效，且時間仍 O(n)。這是前綴和方案相對於滑窗方案的主要優勢。 -
和在 [lo, hi] 範圍內的子陣列數：利用
atMost(hi) - atMost(lo - 1)框架可直接推廣。這與 LC 795（Number of Subarrays with Bounded Maximum）的count(right) - count(left-1)思路完全類比，是「差分計數」的通用技巧。 -
和恰好為 goal 的最短/最長子陣列：若不計個數而是找最短或最長的子陣列，前綴和 + HashMap 方案只需稍作修改：記錄最早/最晚出現的前綴和索引，計算對應的子陣列長度。對二進位陣列而言，最短和為 goal 的子陣列問題等同於找連續 goal 個 1 的情況。