欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【每日一题】和为k的连续子数组——前缀和与滑窗

程序员文章站 2024-03-23 17:58:40
...

2020/05/15 每日一题
对于要求连续子数组的题目,灵活使用前缀和和滑窗的方法。特点在于,前缀和是否递增。

560.和为k的子数组

【每日一题】和为k的连续子数组——前缀和与滑窗

题目需要注意几个关键点,数组元素是既有正数又有负数的且要求是连续的子数组
数组元素既有正数又有负数隐含了意思,数组不是单调的。因此不适合用滑动窗口的方法。**滑窗特点是,固定了左边界以后,右边界找到了一个可行解以后,右边界再靠右边的更大的区间肯定不存在目标值,所以才将左边界继续向右滑。**在这道题里显然没有这个性质。

其次,这里的连续子数组的限制给了我们采用前缀和的空间。我们保存前缀和进行比较即可。
要求presum[i]-k = presum[j]也就是存在[j+1,i]这个子区间的和为k。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ## 看到数组中有连续子数组,因此考虑前缀和的思路
        dic = collections.defaultdict(int)
        dic[0] = 1
        sum_ = 0
        ans = 0
        for num in nums:
            sum_ += num
            if sum_ - k in dic:
                ans += dic[sum_-k]
            # 这里需要注意,先判断再存入当前的数值。否则可能出现问题
            dic[sum_] += 1
        return ans

974 和可被K整除的子数组

【每日一题】和为k的连续子数组——前缀和与滑窗

和上面题目很相似的题目,但是特点在于上一题是查找到特定的数值即可。这道题目的要求是得到被K整除。因此我们虽然采用前缀和的思路,但是记录的并不是前缀和,而是前缀和对k取余的结果。

注意负数的同余,-2%6 = 4,这里不需要额外的处理。

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        # dic存储被5除完的余数
        dic = collections.defaultdict(int)
        dic[0] = 1
        ans = 0
        cur = 0
        for num in A:
            cur += num
            if cur % K in dic:
                ans += dic[cur % K]
            dic[cur%K] += 1
        return ans

乘积小于K的子数组

【每日一题】和为k的连续子数组——前缀和与滑窗

这道题目就存在显著的不同了,首先要求的了是正整数,也就是实现了前缀和是单调的。但是要求查找的难度变大了,需要找出小于某一数值的前缀和,所以再采用前缀和的思路就复杂度增加了,每次需要遍历所有的前缀和,才能找全符合小于的数字。

但是我们知道了单调的特性,就可以采用滑动窗口的方法,固定左侧,每次向右侧扩张。如果超过了,就移动左侧边界。

两个细节:

  1. 如何统计合理解?采用right-left+1,也就是固定了右侧时,我们可以移动左侧界,得到的全都是合理解。
  2. 移动左侧边界的方法。我们需要每次移动左侧边界最多移动到大于右侧一个,这样可以帮助右侧处理掉某一个元素自身就大于bar的情况。
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 对于这种单调增的序列,可以采用滑动窗口的方法
        n = len(nums)
        right = 0
        left = 0
        cur = 1
        ans = 0
        for right, num in enumerate(nums):
            cur *= num
            while cur>=k and left<=right:
                cur /= nums[left]
                left += 1
            ans += right-left+1 
        return ans

上一篇: 砍树(贪心)

下一篇: