【每日一题】和为k的连续子数组——前缀和与滑窗
程序员文章站
2024-03-23 17:58:40
...
2020/05/15 每日一题
对于要求连续子数组的题目,灵活使用前缀和和滑窗的方法。特点在于,前缀和是否递增。
560.和为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取余的结果。
注意负数的同余,-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的子数组
这道题目就存在显著的不同了,首先要求的了是正整数,也就是实现了前缀和是单调的。但是要求查找的难度变大了,需要找出小于某一数值的前缀和,所以再采用前缀和的思路就复杂度增加了,每次需要遍历所有的前缀和,才能找全符合小于的数字。
但是我们知道了单调的特性,就可以采用滑动窗口的方法,固定左侧,每次向右侧扩张。如果超过了,就移动左侧边界。
两个细节:
- 如何统计合理解?采用
right-left+1
,也就是固定了右侧时,我们可以移动左侧界,得到的全都是合理解。 - 移动左侧边界的方法。我们需要每次移动左侧边界最多移动到大于右侧一个,这样可以帮助右侧处理掉某一个元素自身就大于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
上一篇: 砍树(贪心)