Leetcode 1248:统计「优美子数组」(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1248:统计「优美子数组」(超详细的解法!!!)

in leetcode with 0 comment

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

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

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

示例 1:

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

示例 2:

输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。

示例 3:

输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

提示:

解题思路

这个问题的解法和之前问题Leetcode 560:和为K的数组(最详细的解法!!!)一模一样,所以直接在原来的基础上修改即可。

假设我们令P[i] = A[0] + A[1] + ... + A[i-1]P[j] = A[0] + A[1] + ... + A[j-1],那么P[j] - P[i] = A[i] + A[i+1] + ... + A[j-1](其中A数组记录nums中的数是奇数还是偶数,奇数为1,偶数为0)。如果P[j] - P[i] == k的话,那么[i,j]就是我们需要的区间。所以我们对于每个j,我们只要计算有多少个i使得P[j] - P[i] == k,这样我们就得到了P[j]作为右区间并且奇数个数为k的区间数。对于A中的每个元素都做同样的处理,最有将所有的结果相加即可。

具体实现上,我们通过hash_map记录P[j]。初始化的时候要注意一个细节,对于dict[0]=1。为什么?因为当P[j]==k时,P[i]=0并且此时我们的result=1

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        res, cur_sum = 0, 0
        sum_dict = {0:1}
        for num in nums:
            cur_sum += num & 1 # 修改
            if cur_sum - k in sum_dict:
                res += sum_dict[cur_sum - k]
            sum_dict[cur_sum] = sum_dict.get(cur_sum, 0) + 1
        return res

这个问题和Leetcode 992:K 个不同整数的子数组(超详细的解法!!!)也非常类似,我们可以使用这个问题的思想。

我们定义[i,j)这个区间内的元素表示最少的包含K个奇数的子区间,而[i,k)表示最少的包含K+1个奇数的子区间,那么此时以A[i]为起始包含k个奇数的子数组个数有k-j+1个。

那么我们可以先求出最多k个奇数的子数组有$f_m(k)$个,最多k-1个奇数的子数组有$f_m(k-1)$个。那么恰好K个不同整数的解$f_e(k)$就是

为什么要这样做呢?因为最多K个不同整数的子数组这个问题很容易求。那么这个问题怎么求呢?我们同样定义两个指针ij,表示[i,j]区间。首先不断移动j,计算nums[j]是奇数还是偶数,统计奇数的个数。当奇数的个数大于k的时候(此时就是最少的包含K+1个奇数的子区间)。接着移动i,区间[i,j]的奇数个数随之改变,直到奇数个数为k的时候(此时i移动前的位置到当前位置就是最少的包含K个奇数的子区间)。接着再移动j,不断重复上面操作,该过程中不断累加区间个数j-i+1

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(k):
            res = i = 0
            for j in range(len(nums)):
                k -= nums[j] % 2
                while k < 0:
                    k += nums[i] % 2
                    i += 1
                res += j - i + 1
            return res
        return atMost(k) - atMost(k - 1)

reference:

https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419378/JavaC%2B%2BPython-Sliding-Window-atMost(K)-atMost(K-1)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses