?一. 前綴和技巧

（1）前綴和

前綴和技巧適用于快速、頻繁地計算一個索引區間內的元素之和。?

class NumArray {
public:vector<int> preSum; //前綴和數組NumArray(vector<int>& nums) {//preSum[0] = 0，便于計算累加和preSum.resize(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++){preSum[i + 1] = preSum[i] + nums[i];}}int sumRange(int left, int right) {// 查詢閉區間 [left, right] 的累加和return preSum[right + 1] - preSum[left];}
};

（2）前綴和+哈希表

前綴和數組幫你快速計算子數組的元素之和，但如果讓你尋找某個符合條件的子數組，怎么辦？比方說，讓你在?nums?中尋找和為?target?的子數組，就算有前綴和數組的幫助，你也要寫個嵌套 for 循環。但我們可以借助哈希表記錄每個前綴和對應的索引，這樣就能快速計算目標和為?target?的子數組了?

class Solution {
public:int findMaxLength(vector<int>& nums) {int len = 0;vector<int> preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++)preSum[i+1] = preSum[i] + (nums[i] == 0 ? -1 : 1);// 前綴和到索引的映射，方便快速查找所需的前綴和unordered_map<int, int> umap;for(int i = 0; i < preSum.size(); i++){// 如果這個前綴和還沒有對應的索引，說明這個前綴和第一次出現，記錄下來if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = i;else len = max(len, i - umap[preSum[i]]);}return len;}
};

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {vector<int>preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++)preSum[i + 1] = preSum[i] + nums[i];unordered_map<int, int> umap;// 尋找 i, j 使得 (preSum[i] - preSum[j]) % k == 0 且 i - j >= 2// (preSum[i] - preSum[j]) % k == 0 其實就是 preSum[i] % k == preSum[j] % kfor(int i = 0; i < preSum.size(); i++){auto it = umap.find(preSum[i] % k);if(it == umap.end()) umap[preSum[i] % k] = i;else if ((i - it->second) >=2) return true;}return false;}
};

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0;vector<int> preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++){preSum[i + 1] = preSum[i] + nums[i];}// 尋找 i, j 使得 preSum[i] - preSum[j] == k, i > j// nums = [1,2,3], k = 3, preSum = [0,1,3,6]unordered_map<int, int> umap;for(int i = 0; i < preSum.size(); i++){if(umap.find(preSum[i] - k) != umap.end()) ans += umap[preSum[i] - k]; // 該語句必須放在前面if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = 1;else umap[preSum[i]]++;}return ans;}
};

??