一、題目解析

1.子數組是數組中元素的連續非空序列

2.nums[i]范圍為[-1000,1000]，存在負數

3.由于2的題目條件，該題不能用雙指針算法，不具備單調性?

二、算法原理

解法1：暴力解法->枚舉 O(N^2)

固定一個值，向后枚舉數組和，遇到sum == k仍需繼續枚舉，因為后面同樣有可能出現sum == k的情況

解法2：前綴和+哈希表

用哈希表unordered_map<int,int>?hash，統計前綴和出現的頻率

細節問題：

1.前綴和加入哈希表的時機？

在判斷hash表中是否存在sum[i]-k后加入哈希表，即在下一個位置計算前綴和時，哈希表內存儲的是上次的前綴和，也就是[0,i-1]區間的前綴和

2.不用真的創建一個前綴和數組，使用變量sum標記前一個位置的前綴和

3.如果整個前綴和等于k呢？

即在hash中，hash[0]=1

三、代碼示例

class Solution {
public:int subarraySum(vector<int>& nums, int k){unordered_map<int,int> hash;hash[0] = 1;int sum = 0,ret = 0;for(auto e : nums){sum += e;if(hash.count(sum - k)) ret += hash[sum - k];hash[sum]++;}return ret;}
};

?

?

看到最后，如果對您有所幫助，還請點贊、收藏和關注，我們下期再見！?