给定一个长度为 n 的正整数数组 nums 和一个目标整数 k ，返回数组中的 牛连续子数组 的数目。 如果 nums 中的某个连续子数组中不同的整数个数恰好是 k 个，则称这个连续子数组为 牛连续子数组，不同位置的连续子数组可能一样，都算入最终数目里。 数据范围：
区块链毕设网qklbishe.com为您提供问题的解答
给定一个长度为 n 的正整数数组 nums 和一个目标整数 k ，返回数组中的 牛连续子数组 的数目。
如果 nums 中的某个连续子数组中不同的整数个数恰好是 k 个，则称这个连续子数组为 牛连续子数组，不同位置的连续子数组可能一样，都算入最终数目里。
数据范围： 
# -*- coding: utf-8 -*- import collections # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param k int整型 # @return int整型 # class Solution: """ 题目; https://www.nowcoder.com/practice/ac380725961a46a2b0747f803f96d6e7?tpId=196&tqId=40551&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 参考： https://leetcode.cn/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/ 算法： 题目要求：统计nums中 不同字符数为k的连续子数组 的个数 我们对于原问题进行转换： 把「恰好存在 K 个不同整数的子区间」改成「最多存在 K 个不同整数的子区间」就可以使用双指针一前一后交替向右的方法完成，这是因为 对于每一个确定的左边界，最多包含 K 种不同整数的右边界是唯一确定的，并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。 而「最多存在 K 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1 个不同整数的子区间的个数」。 使用双指针（滑动窗口）：定义函数atMostKDistinct(nums, k)表示「最多存在 K 个不同整数的子区间的个数」 返回值： atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1) 复杂度： 时间复杂度：O(n) 空间复杂度：O(k) """ def nowsubarray(self, nums, k): # write code here def atMostKDistinct(k): left, right, n = 0, 0, len(nums) distinct, res, count = 0, 0, collections.Counter() while right < n: if count[nums[right]] == 0: distinct += 1 count[nums[right]] += 1 while distinct > k: count[nums[left]] -= 1 if count[nums[left]] == 0: distinct -= 1 left += 1 res += right - left + 1 # 区间[left, right]上以下标left为起点的子区间有right - left + 1个 right += 1 return res return atMostKDistinct(k) - atMostKDistinct(k - 1) if __name__ == "__main__": sol = Solution() nums, k = [1, 3, 1, 3, 2], 2 # nums, k = [1, 1, 4, 5, 1, 4], 2 # nums, k = [1, 3, 1], 2 res = sol.nowsubarray(nums, k) print res
27:26
以上就是关于问题给定一个长度为 n 的正整数数组 nums 和一个目标整数 k ，返回数组中的 牛连续子数组 的数目。 如果 nums 中的某个连续子数组中不同的整数个数恰好是 k 个，则称这个连续子数组为 牛连续子数组，不同位置的连续子数组可能一样，都算入最终数目里。
数据范围：的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
