523. Continuous Subarray Sum
给一个 array nums 和 k，问你 nums 有没有总合是 k 的倍数的 continuous subarray
这个 subarray 至少要有两个元素
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
[2,4] -> 2+4 = 6
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
[23,2,6,4,7] -> 23+2+6+4+7 = 42
思路:
1.这种算区间总合的应该很直觉能想到用 prefix sum 来记
先对每个 i 算出 presum[i] = nums[0] + nums[1] + ...... + nums[i]
然后就能很轻松的用 presum[j] - presum[i] 得出 nums[j+1] + ...... + nums[i]
建 presum 只需 O(n)
2.如果两层 for-loop iterate i, j 去检查 (presum[j] - presum[i])%k 等不等于 0
这样复杂度是 O(n^2) 看测资范围是不太OK
所以就想有没有办法对 j 一次检查他前面的 i 有没有能跟他配的
如果 presum[j]%k == 3 那我们就知道前面也要找 presum[i]%k == 3
这样就代表 (presum[j] - presum[i])%k == 0
那就简单了 开一个 set 把前面出现过的 presum[i]%k 记起来
后面的 presum[j] 就检查有没有模数跟他一样的
有就能成功配对 没有就把 presum[j]%k 加进 set 里给后面的人挑
这样就只需 iterate 一次
3.题目有另外要求 subarray 至少要有两个元素
也就是说在检查 presum[j] 时 presum[j-1] 不能做他的 candidate
那也很简单 就是检查完隔一回合再把 presum[j-1] 加进 set 就好
这样 presum[j-1] 就不会被 presum[j] 挑到
当然也可以改用 dict 然后顺便记 index
Python code:
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
n = len(nums)
modset = set()
presum = last = 0
for i in range(n):
presum = (presum + nums[i])%k
if presum in modset:
return True
else:
modset.add(last)
last = presum
return False