LeetCode Continuous Subarray Sum | bitJoy > code
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:
- The length of the array won't exceed 10,000.
- 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的约束。
Read full article from LeetCode Continuous Subarray Sum | bitJoy > code
No comments:
Post a Comment