來自leetcode 560
前言
自己只會暴力，這里就是記錄一下前綴和+哈希表的做法，來自靈神的前綴和+哈希表：從兩次遍歷到一次遍歷，附變形題
正文
首先，這道題無法使用滑動窗口，因為滑動窗口需要滿足單調性，當右端點元素進入窗口時，窗口元素和是不能減少的。但是這道題中數組元素可以是負數，因此元素和可能會減少，不滿足單調性，所以無法使用滑動窗口。
暴力
比較容易想到的當然是暴力。兩個for循環，把所有的子數組的和都計算一遍，并判斷和是否為k。暴力直接超時。
前綴和+哈希表
這里，靈神先給了兩數之和的優化思路【動畫】從兩數之和中，我們可以學到什么？，感覺對于理解這道題很有用。
設 i<j，如果 nums[i] 到 nums[j?1] 的元素和等于 k，用前綴和表示，就是
s[j]?s[i]=k。
枚舉 j，上式變成s[i]=s[j]?k。
對于問題【該數組中和為k的子數組的個數】，就可以變相理解為：
對于每個 s[j]，分別計算有多少個 s[i] 滿足 i<j 且 s[i]=s[j]?k（已知 s[j] 和 k，統計 s[0] 到 s[j?1] 中有多少個數等于 s[j]?k），然后再將每個 s[j]計算得到的 s[i] 的個數相加就得到最終答案。
比如有例子：nums=[1,1,?1,1,?1], k=1，其前綴和 s=[0,1,2,1,2,1]。那么流程如下圖，對于每個s[j]判斷前面有幾個s[i]滿足s[i]=s[j]-k。
而哈希表 cnt 的作用就是記錄已經遍歷過的s元素的個數，那么枚舉到 s[j] 時，從哈希表中就可以直接通過 cnt[s[j]?k]找到有幾個 s[i]。因此每次枚舉到s[j]后就把s[j]加入到哈希表中或更新s[j]的個數。
代碼如下，需要兩次遍歷，一次是構建前綴和，一次是遍歷前綴和：
以下代碼只需要一次遍歷，一邊構建前綴和一邊遍歷：
)
