Leetcode【523、525、560、974】

2019-07-10  本文已影响0人  牛奶芝麻

引言：

以下四道 Leetcode 题目属于典型数组问题处理方法。它们采取类似的方法：利用哈希表保存数组前缀（前缀和、前缀01差值、前缀和对K的取余结果等等），然后判断子数组合法性。时间复杂度可以达到 O(n) 级别。

问题描述：【Hash Table】523. Continuous Subarray Sum
解题思路：

这道题是给一个非负整数数组和整数 k，判断数组是否含有连续子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

做法如下：

例1、以 nums = [2,4]，k = 3 举例：

例 1 也说明为什么要在初始化的时候在 Hash Table 中加入 {0: -1}。

例2、以 nums = [5,2,4]，k = 3 举例：

注意，这道题还有几个边界情况：（1）k 可能为负值和 0；（2）数组中可能出现 [0,0] 这种情况。

例3、以 nums = [0, 0]，k = 0 举例：

考虑到上述 3 个例子的情况，我们就可以写出代码了。

Python3 实现：
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        dic = {0: -1}  # 保存前缀和的位置索引，{0:-1}为了处理边界情况
        presum = 0
        for i in range(len(nums)):
            presum += nums[i]
            if k != 0:  # k非0才对前缀和进行求余操作
                presum %= k
            if presum in dic:  # 前缀和在dic中找到，说明当前位置与dic[presum]之间数字之和为k
                if i - dic[presum] >= 2:  # 还要满足长度大于等于2
                    return True
            else:
                dic[presum] = i
        return False
问题描述：【Hash Table】525. Contiguous Array
解题思路：

这道题是给一个 01 数组，求含有相同数量的 0 和 1 的最长连续子数组的长度。

方法1（前缀 01 差值）：

例如，nums = [1,1,0,0,0,1]，cnt = [0, 0] 统计前缀 01 个数，对于每个位置 i：

Python3 实现：

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        dic = {0: -1}  # 保存01差值的位置索引，{0:-1}为了处理边界情况
        cnt = [0, 0]  # 统计01次数
        max_ = 0
        for k, num in enumerate(nums):
            cnt[num] += 1  # 01计数
            sub = cnt[0] - cnt[1]  # 计算0与1的差值，可能为负值
            if sub not in dic:
                dic[sub] = k
            else:
                max_ = max(max_, k - dic[sub])
        return max_

方法2（前缀和为0）：

如果我们把数组中的所有 0 全部变成 -1，那么这道题就变成了求和为 0 的最长连续子数组长度。那么类似于上面的 Leetcode 523，我们计算前缀和，判断前缀和是否在 Hash Table 中再次出现，如果再次出现，说明两位置之间的和为 0，即两位置之间01个数相同，则更新最大长度；否则，将前缀和保存在 Hash Table 中。

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        dic = {0: -1}  # 保存前缀和的位置索引，{0:-1}为了处理边界情况
        presum, max_ = 0, 0
        for k, num in enumerate(nums):
            if num == 0:  # 把0改成-1计算前缀和
                presum += (-1)
            else:
                presum += 1
            if presum not in dic:
                dic[presum] = k
            else:  # 前缀和再次出现，说明两位置之间和为0，即01个数相等
                max_ = max(max_, k - dic[presum])
        return max_
问题描述：【Hash Table】560. Subarray Sum Equals K
解题思路：

这道题是给一个数组，求连续子数组和为 k 的总数。

这道题和 Leetcode 523 以及 Leetcode 525 的方法 2 类似，也是先求前缀和 presum，但是区别在于，前面两道题判断 presum 是否再次出现在 Hash Table 中，但是这道题要判断 presum - k 是否再次出现在 Hash Table 中。并且，还有一点不同的是，因为要计算子数组的总数，所以 Hash Table 中的键还是前缀和 presum，但是值要存储当前前缀和出现的次数，而不像前两道题中存储当前位置索引。初始化时，Hash Table 中 {0: 1}，用于边界情况处理。

举个例子：nums = [2, 4, 1, 0, 5, -7]，k = 5

Python3 实现：
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = {0: 1}  # 保存前缀和出现次数，{0:-1}为边界情况
        presum, ans = 0, 0
        for num in nums:
            presum += num
            if (presum - k) in dic:  # 前缀和减去目标值在dic中找到，累加结果
                ans += dic[presum-k]
            if presum not in dic:  # 将前缀和出现次数保存到dic中
                dic[presum] = 1
            else:
                dic[presum] += 1
        return ans
问题描述：【Hash Table】974. Subarray Sums Divisible by K
解题思路：

这道题是给一个数组，求连续子数组之和可以被 K 整除的总数。

经过了上面三道题的历练，这道题自然很容易求解。题目中“连续子数组之和可以被 K 整除”类似于 Leetcode 523 的做法，要先将前缀和 presum 对 K 取余，并且判断 presum 是否在 Hash Table 中出现过；而它是一个计算总数的问题，类似于 Leetcode 560，Hash Table 中保存的应该是前缀和出现的次数。因此，很快可以写出代码。

Python3 实现：
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        dic = collections.defaultdict(int)
        dic[0] = 1
        ans, presum = 0, 0
        for a in A:
            presum += a
            presum %= K  # 先将前缀和对K取余
            if presum in dic:
                ans += dic[presum]
            dic[presum] += 1  # 统计前缀和出现次数
        return ans

总结：

计算数组前缀（前缀和、前缀01差值、前缀和对K的取余结果等等）保存在 Hash Table 中，等到下次再次出现相同的前缀时，说明两次位置之间的数字是满足题意的。利用这个特点，我们能做到在 O(n) 的时间内求解。

上一篇下一篇

猜你喜欢

热点阅读