題意：給定一個(gè)數(shù)組求連續(xù)的子數(shù)組的和為k的有幾個(gè)
Input: nums = [1,1,1], k = 2
Output: 2

https://leetcode.com/problems/subarray-sum-equals-k/description/

首先思考1.因?yàn)槭莝ubarray sum前綴和很容易想到，那問(wèn)題就轉(zhuǎn)化成preSum[i] = preSum[j] - k (i < j)求個(gè)數(shù)的問(wèn)題，那么hashmap就很容易想到了
思考2: dp，但是dp在這里有個(gè)問(wèn)題，1維dp是沒有辦法解決這個(gè)問(wèn)題的，這種類型的dp一般是dp[i]，意思是以右端點(diǎn)為i的subarray sum，但是dp[i]找不到任何可以遞推的等式，所以必須引入左端點(diǎn)做二維dp，那么問(wèn)題的復(fù)雜度就高了
還有一個(gè)點(diǎn)是，第二個(gè)for循環(huán)中，必須要引入preSum[0], 因?yàn)?code>preSum[i] - preSum[0]是0-i的數(shù)字全包括的情況

class Solution {
public:int subarraySum(vector<int>& nums, int k) {//preSum[j] - preSum[i] = k//preSum[i] = preSum[j] - k (i < j)int m = nums.size();vector<int> preSum(m+1, 0);preSum[0] = 0;for(int i = 1; i < preSum.size(); i++) {preSum[i] = preSum[i-1] + nums[i-1]; }int ret = 0;unordered_map<int, int> mp;for(int i = 0; i < preSum.size(); i++) {if(mp.count(preSum[i]-k) > 0) {ret += mp[preSum[i]-k];}mp[preSum[i]]++;}return ret;}
};

時(shí)間O(n), 空間O(n)