[LeetCode]Continuous Subarray Sum

和subarray sum equals k是很类似的，区别在于我们这要考虑倍数。首先要特殊对待负数的情况。直接取绝对值即可。还有0的情况，我们待会讲。那么我们每次去map中找presum的时候，要找当前presum - k * n的值，也就是有presum/k个数需要去找，那么当presum很大k很小的时候复杂度会大大提高，所以这里我们考虑其他的思路来简化。既然我们有公式presum1 - presum2 = k * n，当k不等于0的时候，对两边取余，我们有presum1 % k = presum2 % k，所以我们只要对数组所有数取余，寻找和当前presum相等的presum即可:

• 如果坐标相差大于1说明我们找到了
• 否则，说明只是当前的数是k的倍数，不满足size大于等于2的条件。这种情况下我们什么都不需要做，因为我们没有必要让其对应的index变得更大

对于k=0的情况，我们也是寻找相等的presum，所以是一样的。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	bool checkSubarraySum(vector<int>& nums, int k) {
	int len = nums.size(), sum = 0;
	k = abs(k);
	unordered_map<int, int> map;
	map[0] = -1;
	for(int i = 0; i < len; ++i)
	{
	sum += nums[i];
	if(k)
	sum %= k;
	if(map.find(sum) != map.end())
	{
	if(i - map[sum] > 1)
	return true;
	//if not we don't do anything
	//since we don't want to update the index
	//to be larger
	}
	else
	map[sum] = i;
	}
	return false;
	}
	};

view raw Continuous Subarray Sum.cpp hosted with ❤ by GitHub