Leetcode 523 Continuous Subarray Sum

发表于 |

给定一个包含非负数的数组和一个目标整数k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为2，总和为k的倍数，即总和为 n*k，其中n也是一个整数。

示例 1:
输入: [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。

说明:

  1. 数组的长度不会超过10,000。
  2. 你可以认为所有数字总和在 32 位有符号整数范围内。

分析：

  1. 这道题和560题解法一样，强烈建议先看那道题，具体见https://leetcode.com/problems/subarray-sum-equals-k/solution/
  2. 当我们分析数组中连续的若干数之和时，很容易想到先用一个数组sm[i]记录sum(nums[:i])，那么则有sm[j] - sm[i] = sum(nums[i:j])
  3. 但是如果依次遍历时间复杂度为O(n^2)，在这里肯定超时，所以我们得想个简单的办法，这也就是这类型题的经典思想，前缀和处理
  4. 我们先来考虑一个简单的情况，即是否存在连续的子数组的和为k，我们应该怎么做呢？
    1. 假设存在i,j满足sum(nums[i:j]) = k，那么则应有sm[j] - sm[i] = k，也就是如果我们找到i,j满足这个式子就可以说明存在…！
    2. 那当我们遍历sm数组时，将遍历的数依次存进集合，遍历至sm[j]时，我们如果发现sm[j]-k，即sm[i]是存在于集合中的，那么我们就可以确定,确实存在sum(nums[i:j]) = k
  5. 回到我们这道题上，假设确实存在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

思路：

  1. 因为j-i>=2，所以更新集合的时候应当推迟一步，即分析完sm[i]之后才将sm[i-1]%k加入集合之中
  2. 注意k = 0的情况，因为模0操作是不被允许的，所以需要单独处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class 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


75 / 75 test cases passed.
difficulty: medium
Runtime: 36 ms,beats 98%