LeetCode #560.和為k的子數(shù)組

題目描述：

給你一個整數(shù)數(shù)組?nums?和一個整數(shù)?k?，請你統(tǒng)計并返回?該數(shù)組中和為?k?的連續(xù)子數(shù)組的個數(shù)?。

子數(shù)組是數(shù)組中元素的連續(xù)非空序列。

思路：

1. 用Python寫的，上來就暴力解法，果然時間超時，放棄。

2. 用了前綴和數(shù)組求數(shù)組范圍之和，時間超時，換C++，還是超時，放棄。

3. 一番掙扎，上網(wǎng)搜索，恍然大悟，做個筆記，記錄解法。

解法：

用一個字典記錄遍歷的所有前綴和及其出現(xiàn)次數(shù)，假設當前前綴和為A，如果存在到A的子數(shù)組的和為k的話，那么必定存在前綴和為A-k，數(shù)量為字典中記錄的值。

代碼如下：

如侵刪，歡迎評論指正。