[Leetcode] 560 Subarray Sum Equals K

题意：给定一个数组求连续的子数组的和为k的有几个
Input: nums = [1,1,1], k = 2
Output: 2

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

首先思考1.因为是subarray sum前缀和很容易想到，那问题就转化成preSum[i] = preSum[j] - k (i < j)求个数的问题，那么hashmap就很容易想到了
思考2: dp，但是dp在这里有个问题，1维dp是没有办法解决这个问题的，这种类型的dp一般是dp[i]，意思是以右端点为i的subarray sum，但是dp[i]找不到任何可以递推的等式，所以必须引入左端点做二维dp，那么问题的复杂度就高了
还有一个点是，第二个for循环中，必须要引入preSum[0], 因为preSum[i] - preSum[0]是0-i的数字全包括的情况

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;}
};

时间O(n), 空间O(n)