[LeetCode]Subarray Sum Equals K

contiguous subarray的题很多都和presum有管，因为用presum预处理后能O(1)时间算出区间和。这道题也是一样，先presum预处理，同时用map记录，然后每一次去map里查有没有presum可以使差为k，代表着存在区间和是k的连续区间。空间时间复杂度都是O(n)，代码如下：

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

view raw Subarray Sum Equals K.cpp hosted with ❤ by GitHub