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
前面有可能存在一個下标
k
,滿足
[k,i]
這個子數組的數字和為
k
,這樣就不難了解為什麼每次都需要累加
pre[i-1]
的次數了.(注意這個
pre[i-1]
的值是通過
pre[j]-k
來得到的)
4.如果還沒了解為什麼要累加
pre[i-1]
出現的次數，來張圖感受一下。
觀看上圖，假設我們已經知道
OA
、
OB
、
OC
的長度均為
s
，那麼我們可取距離
C
點為
k
的點
D
，可知
AD=BD=CD=k
，通過這個圖就很好了解為什麼要累加
pre[j]-k
出現的次數了。
5.這道題當初做的時候了解錯題目了,原以為是求出連續的符合條件的子數組，并且子數組之間邊界恰好重疊。其實這道題說的是這個子數組連續,也就是說這個子數組它不間斷,否則沒有了解到這點就很難做對了。
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;
}
}; 複制