大家好，我是吳師兄，

今天的題目來源于 LeetCode 第 560 號(hào)問題：和為 K 的子數(shù)組，難度為「中等」。

一、題目描述

給你一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)k，請(qǐng)你統(tǒng)計(jì)并返回該數(shù)組中和為k的子數(shù)組的個(gè)數(shù)。

示例 1：

輸入：nums =[1,1,1], k = 2
輸出：2

示例 2：

輸入：nums =[1,2,3], k = 3
輸出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

二、題目解析

補(bǔ)充知識(shí)點(diǎn)前綴和：前綴和指一個(gè)數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和（包含其自身）。

利用前綴和這種特點(diǎn)，可以快速的計(jì)算某個(gè)區(qū)間內(nèi)的和，比如前 i 個(gè)元素的前綴和為preSum[i] = num[0] + nums[1] + ... + nums[i]，而前 j 個(gè)元素的前綴和為preSum[j] = num[0] + nums[1] + ... + nums[j]。

那么區(qū)間[ i , j ]之間的子數(shù)組之和就是 **preSum[j] - preSum[i]**。

基于這種思路，可以先遍歷一次數(shù)組，求出前綴和數(shù)組。

題目這個(gè)時(shí)候就變成了需要尋找出多少個(gè) i 和 j 的組合，使得 [ i , j ] 這個(gè)區(qū)間的和為 k。

classSolution{
publicintsubarraySum(int[]nums,intk){

intlen=nums.length;

int[]preSum=newint[len+1];

preSum[0]=0;

for(inti=0;i1]=preSum[i]+nums[i];
}

intcount=0;

for(inti=0;ifor(intj=i;jif(preSum[j+1]-preSum[i]==k){
count++;
}
}
}
returncount;
}
}

在計(jì)算過程中，有兩個(gè) for 循環(huán)發(fā)生了嵌套，時(shí)間復(fù)雜度來到了 O(n^2) 級(jí)別。

需要優(yōu)化。

事實(shí)上，我們不需要去計(jì)算出具體是哪兩項(xiàng)的前綴和之差等于k，只需要知道等于 k 的前綴和之差出現(xiàn)的次數(shù) count，所以我們可以在遍歷數(shù)組過程中，先去計(jì)算以 nums[i] 結(jié)尾的前綴和 pre，然后再去判斷之前有沒有存儲(chǔ) pre - k 這種前綴和，如果有，那么 pre - k 到 pre 這中間的元素和就是 k 了。

具體操作如下：

1、利用哈希表，以前綴和為鍵，出現(xiàn)次數(shù)為對(duì)應(yīng)的值，記錄 pre[i] 出現(xiàn)的次數(shù)。

2、開始從頭到尾遍歷 nums 數(shù)組，在遍歷過程中，會(huì)執(zhí)行兩個(gè)操作。

3、存儲(chǔ)索引為 i 的這個(gè)元素時(shí)，前綴和的值是多少，并且把這個(gè)值出現(xiàn)的頻次存儲(chǔ)到 mp 中。

4、判斷之前有沒有存儲(chǔ) pre - k 這種前綴和，如果有，說明 pre - k 到 pre 直接的那些元素值之和就是 k。

5、返回結(jié)果。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//和為 K 的子數(shù)組（LeetCode 560）：https://leetcode.cn/problems/subarray-sum-equals-k/
classSolution{
publicintsubarraySum(int[]nums,intk){

//統(tǒng)計(jì)和為K的子數(shù)組的數(shù)量
intcount=0;

//記錄遍歷到索引為i的這個(gè)元素時(shí)，前綴和的值是多少
intpre=0;

//利用哈希表，以前綴和為鍵，出現(xiàn)次數(shù)為對(duì)應(yīng)的值，記錄pre[i]出現(xiàn)的次數(shù)
HashMapmp=newHashMap<>();

//一開始，需要設(shè)置前綴和為0時(shí)，出現(xiàn)的次數(shù)為1次
//這一行的作用就是為了應(yīng)對(duì)nums[0]+nums[1]+...+nums[i]==k這種情況
//如數(shù)組[1,2,3,6]
//這個(gè)數(shù)組的累加和數(shù)組為[1,3,【6】,12]
//如果k=6,假如mp中沒有預(yù)先存儲(chǔ)(0,1)
//那么來到累加和為6的位置時(shí)，這時(shí)mp中存儲(chǔ)的就只有兩個(gè)數(shù)據(jù)(1,1),(3,1)
//想去判斷mp.containsKey(pre-k),這時(shí)pre-k=6-6=0
//但map中沒有(0,1)，
//因?yàn)檫@個(gè)時(shí)候忽略了從下標(biāo)0累加到下標(biāo)i等于k的情況
//僅僅是統(tǒng)計(jì)了從下標(biāo)大于0到某個(gè)位置等于k的所有答案
mp.put(0,1);

//開始從頭到尾遍歷nums數(shù)組，在遍歷過程中，會(huì)執(zhí)行兩個(gè)操作
//1、存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少，并且把這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
//2、判斷之前有沒有存儲(chǔ)pre-k這種前綴和，如果有，說明pre-k到pre直接的那些元素值之和就是k
for(inti=0;i//存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少
pre+=nums[i];

//判斷之前有沒有存儲(chǔ)pre-k這種前綴和
if(mp.containsKey(pre-k)){

//如果有，說明pre-k到pre直接的那些元素值之和就是k
//找到了一組，累加到count上
count+=mp.get(pre-k);

}

//這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
// getOrDefault：當(dāng) Map 集合中有這個(gè) key 時(shí)，就使用這個(gè) key 對(duì)應(yīng)的 value 值
//如果沒有就使用默認(rèn)值defaultValue
mp.put(pre,mp.getOrDefault(pre,0)+1);
}

//返回結(jié)果
returncount;
}
}

2、C++ 代碼

classSolution{
public:
intsubarraySum(vector<int>&nums,intk){

//統(tǒng)計(jì)和為K的子數(shù)組的數(shù)量
intcount=0;

//記錄遍歷到索引為i的這個(gè)元素時(shí)，前綴和的值是多少
intpre=0;

//利用哈希表，以前綴和為鍵，出現(xiàn)次數(shù)為對(duì)應(yīng)的值，記錄pre[i]出現(xiàn)的次數(shù)
unordered_map<int,int>mp;

//一開始，需要設(shè)置前綴和為0時(shí)，出現(xiàn)的次數(shù)為1次
//這一行的作用就是為了應(yīng)對(duì)nums[0]+nums[1]+...+nums[i]==k這種情況
//如數(shù)組[1,2,3,6]
//這個(gè)數(shù)組的累加和數(shù)組為[1,3,【6】,12]
//如果k=6,假如mp中沒有預(yù)先存儲(chǔ)(0,1)
//那么來到累加和為6的位置時(shí)，這時(shí)mp中存儲(chǔ)的就只有兩個(gè)數(shù)據(jù)(1,1),(3,1)
//想去判斷mp.containsKey(pre-k),這時(shí)pre-k=6-6=0
//但map中沒有(0,1)，
//因?yàn)檫@個(gè)時(shí)候忽略了從下標(biāo)0累加到下標(biāo)i等于k的情況
//僅僅是統(tǒng)計(jì)了從下標(biāo)大于0到某個(gè)位置等于k的所有答案
mp[0]=1;

//開始從頭到尾遍歷nums數(shù)組，在遍歷過程中，會(huì)執(zhí)行兩個(gè)操作
//1、存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少，并且把這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
//2、判斷之前有沒有存儲(chǔ)pre-k這種前綴和，如果有，說明pre-k到pre直接的那些元素值之和就是k
for(inti=0;i//存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少
pre+=nums[i];

//判斷之前有沒有存儲(chǔ)pre-k這種前綴和
if(mp.find(pre-k)!=mp.end()){

//如果有，說明pre-k到pre直接的那些元素值之和就是k
//找到了一組，累加到count上
count+=mp[pre-k];

}

//這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
mp[pre]++;
}

//返回結(jié)果
returncount;

}
};

3、Python 代碼

classSolution:
defsubarraySum(self,nums:List[int],k:int)->int:
#統(tǒng)計(jì)和為K的子數(shù)組的數(shù)量
count=0

#記錄遍歷到索引為i的這個(gè)元素時(shí)，前綴和的值是多少
pre=0

#利用哈希表，以前綴和為鍵，出現(xiàn)次數(shù)為對(duì)應(yīng)的值，記錄pre[i]出現(xiàn)的次數(shù)
mp=collections.defaultdict(int)

#一開始，需要設(shè)置前綴和為0時(shí)，出現(xiàn)的次數(shù)為1次
#這一行的作用就是為了應(yīng)對(duì)nums[0]+nums[1]+...+nums[i]==k這種情況
#如數(shù)組[1,2,3,6]
#這個(gè)數(shù)組的累加和數(shù)組為[1,3,【6】,12]
#如果k=6,假如mp中沒有預(yù)先存儲(chǔ)(0,1)
#那么來到累加和為6的位置時(shí)，這時(shí)mp中存儲(chǔ)的就只有兩個(gè)數(shù)據(jù)(1,1),(3,1)
#想去判斷mp.containsKey(pre-k),這時(shí)pre-k=6-6=0
#但map中沒有(0,1)，
#因?yàn)檫@個(gè)時(shí)候忽略了從下標(biāo)0累加到下標(biāo)i等于k的情況
#僅僅是統(tǒng)計(jì)了從下標(biāo)大于0到某個(gè)位置等于k的所有答案
mp[0]=1

#開始從頭到尾遍歷nums數(shù)組，在遍歷過程中，會(huì)執(zhí)行兩個(gè)操作
#1、存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少，并且把這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
#2、判斷之前有沒有存儲(chǔ)pre-k這種前綴和，如果有，說明pre-k到pre直接的那些元素值之和就是k
foriinrange(len(nums)):

#存儲(chǔ)索引為i的這個(gè)元素時(shí)，前綴和的值是多少
pre+=nums[i]

#判斷之前有沒有存儲(chǔ)pre-k這種前綴和
#如果有，說明pre-k到pre直接的那些元素值之和就是k
#找到了一組，累加到count上
#利用defaultdict的特性，當(dāng)presum-k不存在時(shí)，返回的是0
count+=mp[pre-k]

#這個(gè)值出現(xiàn)的頻次存儲(chǔ)到mp中
# getOrDefault：當(dāng) Map 集合中有這個(gè) key 時(shí)，就使用這個(gè) key 對(duì)應(yīng)的 value 值
#如果沒有就使用默認(rèn)值defaultValue
mp[pre]+=1

#返回結(jié)果
returncount

四、復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，其中 n 為數(shù)組的長(zhǎng)度。我們遍歷數(shù)組的時(shí)間復(fù)雜度為 O(n)，中間利用哈希表查詢刪除的復(fù)雜度均為 O(1)，因此總時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：O(n)，其中 n 為數(shù)組的長(zhǎng)度。哈希表在最壞情況下可能有 n 個(gè)不同的鍵值，因此需要 O(n) 的空間復(fù)雜度。