LeetCode Continuous Subarray Sum

LeetCode Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

  1. The length of the array won't exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

给定一个非负整数数组和k,问数组中是否存在长度至少为2的连续子数组,子数组的和是k的n倍,n也是一个整数。

这个题之前好像在哪遇到过。遇到连续子数组的问题,首先要想到前缀和。因为这里要求和是k的n倍,有点麻烦。

首先我们需要知道一个数学知识,如果到i的前缀和accusum1和到j的前缀和accusum2除以k的余数相等,那么(i,j]的连续子数组的和就是k的整数倍。比如第一个样例中,连续子数组的和以及连续子数组的和除以k的余数:

  • [23,25,29,35,42]
  • [5,1,5,5,0]

如果下标从0开始,则下标为0和2的accusum%k都等于5,说明(0,2]的连续子数组的和是k的整数倍。accusum(0,2]=2+4=6,确实是6的整数倍。

这个道理其实很好理解,accusum0%k=5,到了accusum2%k还等于5,说明中间只加了整数倍的k,才导致余数没变,因为整数倍的k 模k是等于0的。

知道了这个道理就好办了,我们用map保存accusum%k的值和计算到现在的accusum的下标,如果后来遇到一个accusum模k的余数在map中,说明找到了一个可能,我们再判断一下他们之间的距离是否至少为2即可。

还有一个特殊的地方需要注意的是,如果k等于0,则不能取模运算。

最后还要注意的一点是,第12行,把当前余数和下标插入map是在else分支的,只有当map中不存在这个余数才插入,否则不插入。比如上面的例子,我们遇到多个accusum模k的余数是5,但是我们map中保存的应该是第0个下标,后续的余数等于5的下标不能更新0这个下标,因为这样才能使得后续的余数相等的下标和map中的下标的差越大,即更好的满足距离至少为2的约束。

完整代码如下:

class Solution {
public:
	bool checkSubarraySum(vector<int>& nums, int k) {
		unordered_map<int, int> reminders;
		reminders[0] = -1;
		int accusum = 0;
		for (int i = 0; i < nums.size(); ++i) {
			accusum += nums[i];
			if (k != 0)accusum %= k; // 注意k为0时,不能取模
			if (reminders.find(accusum) != reminders.end()) {
				if (i - reminders[accusum] >= 2)return true;
			} else reminders[accusum] = i; // 注意必须是在else分支
		}
		return false;
	}
};

本代码提交AC,用时26MS。

Leave a Reply

Your email address will not be published. Required fields are marked *