leetcode560.和為K的子陣列
題目鏈接
演算法
前綴和+哈希
時間復雜度O(n)，
在解決這道題前需要先清楚，一個和為k的子陣列即為一對前綴和的差值，
1.我們假設有這么一個子陣列[i,j]滿足數字和為k，那么就有pre[j] - pre[i-1] = k（注:pre陣列為記錄前綴和的陣列），則pre[i-1] = pre[j] - k；
2.題目問找到nums陣列中和為k的連續的子陣列的數目,一開始想到是否會重疊，后來仔細看題目后發現題目中并沒有限定子陣列是否重疊，那么這道題只需要記錄pre[i-1]出現的次數即可；
3.不過為什么要累加pre[i-1]出現的次數呢?
原因是我們要算出滿足以下標為j為結尾的陣列的數字和為k的出現的次數,由pre[i-1] = pre[j] - k可知[i,j]這個子陣列已經滿足數字和為k,那么首先需要想到的是應該把這一次記錄上,即+1,不過由于在遍歷時我們每次都會把當前的前綴和用一個哈希表存盤下來,并且累加1,這里我們每次都累加1,也就是說在下標i前面有可能存在一個下標m,滿足[m,i]這個子陣列的數字和為k,這樣就不難理解為什么每次都需要累加pre[i-1]的次數了.(注意這個pre[i-1]的值是通過pre[j]-k來得到的)
4.這道題當初做的時候理解錯題目了,原以為是求出連續的符合條件的子陣列，并且子陣列之間邊界恰好重疊，其實這道題說的是這個子陣列連續,也就是說這個子陣列它不間斷,否則沒有理解到這點就很難做對了，
C++代碼
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
int sum = 0; //記錄當前位置的前綴和
int res = 0;
unordered_map<int,int> hs;
hs[0] = 1; //表示和為0出現1次
for(int i = 0; i < len; i++){
sum += nums[i];
if(hs.find(sum - k) != hs.end()){
res += hs[sum-k];
}
hs[sum]++;
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95798.html
標籤：其他
下一篇：一文學懂遞回和動態規劃