題目敘述
題目會給定一個陣列nums和一個目標值goal。
要求我們計算子陣列總和=goal的數目有多少？
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
Example 2:
Input: nums = [0,0,0,0,0], goal = 0
Output: 15
約束條件
Constraints:
1 <= nums.length <= 3 * 10^4
輸入陣列長度介於1~三萬。
nums[i]is either0or1.
陣列元素要嘛為0，要嘛為1。
0 <= goal <= nums.length
目標值goal介於0~陣列長度之間。
演算法 前綴和 + 字典
這題會用到以前學過的前綴和技巧。(和前面那題用到的觀念是類似的)
從左到右滾動依序計算前綴和，並且把每個前綴和出現的次數存到字典裡面。
如果當下在某個位置前綴和為S，而且在字典裡面又發現前面曾經看過前綴和S-goal，
那麼代表從前面到現在這個位置，存在有滿足條件的子陣列，而且子陣列的總和為goal。
例如:
給定nums=[1, 0, 1, 1], goal = 2
前綴和 = [1, 0, 2, 3]
可以找出子陣列goal = 2的部分為
[1, 0, 1],
[0, 1, 1]
[1, 1]
總共有三個子陣列滿足條件，子陣列區間總和為2。
程式碼 前綴和 + 字典
class Solution:
def numSubarraysWithSum(self, nums, goal):
## Dictionary
# key: prefixSum
# value: occurrence of specific prefixSum
OccOfprefixSum = defaultdict(int)
# Prefix 0 is satisfied by taking nothing
OccOfprefixSum[0] = 1
count, prefixSum = 0, 0
for number in nums:
# update prefixSum so far
prefixSum += number
# If we've seen "prefixSum-goal" before, then subarray with goal must exist
count += OccOfprefixSum[prefixSum-goal]
# Update occurrence of current prefixSum
OccOfprefixSum[prefixSum] += 1
# Total count of subarray with summation = goal
return count
複雜度分析 前綴和 + 字典
時間複雜度:
線性掃描，所需時間為O(n)。
空間複雜度:
需要建立一個前綴和字典，所需空間為O(n)。
關鍵知識點
如果當下在某個位置前綴和為S，而且在字典裡面又發現前面曾經看過前綴和S-goal，
那麼代表從前面到現在這個位置，存在有滿足條件的子陣列，而且子陣列的總和為goal。
Reference:
