title: 和為k的子陣列
?? 題目描述
題目鏈接：和為k的子陣列、leetcode一樣的題目
?? 解題思路
連續子陣列、達到一定值，這些條件好像都是滑動視窗的暗示啊，實際上，不能用滑動視窗！原因：滑動視窗必須都是正數或者負數，因為這樣左右指標單向滑動才能一個負責增大 一個負責減少！
解法：前綴和 + 哈希表
通過pre計算前綴，同時不斷將前綴加入哈希表mp中，哈希表存盤的就是前綴的和，通過：當前遍歷到的前綴pre - 中間子陣列k =前面的前綴 來求解！
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1; //確保可以 以第一個元素未子陣列左邊界
int res = 0, pre = 0; // pre為前綴和
for (int i = 0; i < nums.size(); i++) {
pre += nums[i];
if (mp.find(pre - k) != mp.end()) res += mp[pre - k];
mp[pre]++;
}
return res;
}
};
圖示：
?? 復雜度分析
- 時間復雜度：o(n);
- 空間復雜度：O(n);
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/470658.html
標籤：其他
上一篇：mysql udf提權