转载自王琛_Leetcode 523 Continuous Subarray Sum
给定一个包含非负数的数组和一个目标整数k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为2，总和为k的倍数，即总和为 n*k，其中n也是一个整数。
示例 1:dsagasg
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2:
输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明:
- 数组的长度不会超过10,000。
- 你可以认为所有数字总和在 32 位有符号整数范围内。
分析:
- 这道题和560题解法一样，强烈建议先看那道题，具体见https://leetcode.com/problems/subarray-sum-equals-k/solution/
- 当我们分析数组中连续的若干数之和时，很容易想到先用一个数组sm[i]记录sum(nums[:i])，那么则有sm[j] - sm[i] = sum(nums[i:j])
- 但是如果依次遍历时间复杂度为O(n^2)，在这里肯定超时，所以我们得想个简单的办法，这也就是这类型题的经典思想，前缀和处理
- 我们先来考虑一个简单的情况，即是否存在连续的子数组的和为k，我们应该怎么做呢？
- 假设存在i,j满足sum(nums[i:j]) = k，那么则应有sm[j] - sm[i] = k，也就是如果我们找到i,j满足这个式子就可以说明存在…！
- 那当我们遍历sm数组时，将遍历的数依次存进集合，遍历至sm[j]时，我们如果发现sm[j]-k，即sm[i]是存在于集合中的，那么我们就可以确定,确实存在sum(nums[i:j]) = k
- 回到我们这道题上，假设确实存在i,j(j-i>=2)满足sum(nums[i:j]) = n * k，即sm[j] - sm[i] = n * k，此时用上面的方法是不可行的，因为n*k是个不确定的数，我们无法判断其是否在集合内，但我们只用作一个小小的变换————对上式两边同时模k，上式变为sm[j]%k - sm[i]%k = 0，此时就和4中情况是等价的，唯独是集合中存储的数从sm[i]变成了sm[i]%k
思路:
- 因为j-i>=2，所以更新集合的时候应当推迟一步，即分析完sm[i]之后才将sm[i-1]%k加入集合之中
- 注意k = 0的情况，因为模0操作是不被允许的，所以需要单独处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 0: return '00' in ''.join(map(str,nums))
# 初始化集合和前缀和数组
s = set([0])
sm = [nums[0]] * len(nums)
for i in range(1,len(nums)):
sm[i] = sm[i-1] + nums[i]
if sm[i] % k in s:
return True
# 分析完之后再更新集合
s.add(sm[i-1]%k)
return False
- 本文作者： Jason
- 本文链接： https://caicaijason.github.io/2019/10/08/leetcode523/
- 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！