1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 1248. 统计「优美子数组」

1248. 统计「优美子数组」

链接:https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
难度:中等

题目

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

思路

优美子数组的定义是连续子数组中恰好有K个奇数数字。注意这里是连续字数组。

我们可以先对数组中的奇数位置进行记录

以例子为示:

nums = [1,1,2,1,1], k = 3

我们遍历数组中的奇数:

[]               [0]  0为标志位
[1]             [0,1]
[1,1]           [0,1,2]
[1,1,2]         [0,1,2]
[1,1,2,1]      [0,1,2,4]
[1,1,2,1,1]    [0,1,2,4,5]
[1,1,2,1,1]    [0,1,2,4,5,6] 把长度+1加在后面做标志位

然后我们来数优美子数组的个数。

因为k=3,所有其实我们需要找到连续的两个边界,如果找到第 i 个奇数的位置,找到第i+k-1个奇数的位置,这就确定了两个边界,再看这两个边界的活动范围有多大就知道有几种组合了。

左边界的活动范围在当前第 i 个奇数到上一个奇数(即 i-1)之间,右边界的活动范围在当前第 i+k-1 到下一个边界(即 i+k)之间,左边范围 * 右边活动范围累加就是结果。

在这个例子中,

count = (1-0)*(5-4)+(2-1)*(6-5) = 2

代码见解决方案

方案代码

解决方案:

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odd_positions = [0] 
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                odd_positions.append(i + 1)  
        odd_positions.append(len(nums) + 1) 
        count = 0
        for i in range(1, len(odd_positions) - k):
            count += ((odd_positions[i] - odd_positions[i - 1]) *
                      (odd_positions[i + k] - odd_positions[i + k - 1]))  # 组合数
        return count

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/342.html