leetcode怎么解决K个不同整数的子数组
这篇文章主要介绍“leetcode怎么解决K 个不同整数的子数组”,在日常操作中,相信很多人在leetcode怎么解决K 个不同整数的子数组问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”leetcode怎么解决K 个不同整数的子数组”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
成都创新互联专注为客户提供全方位的互联网综合服务,包含不限于做网站、成都网站建设、延安网络推广、成都小程序开发、延安网络营销、延安企业策划、延安品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;成都创新互联为所有大学生创业者提供延安建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com
一、题目内容
给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。
(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。)
返回 A 中好子数组的数目。
示例 1:
输入:A = [1,2,1,2,3], K = 2
输出:7
解释:恰好由 2 个不同整数组成的子数组:[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2:
输入:A = [1,2,1,3,4], K = 3
输出:3
解释:恰好由 3 个不同整数组成的子数组:[1,2,1,3], [2,1,3], [1,3,4].
提示:
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
二、解题思路
最多存在 K 个不同整数的子区间的个数与恰好存在K个不同整数的子区间的个数的差恰好等于最多存在 K - 1个不同整数的子区间的个数。
因此,最多存在 K 个不同整数的子区间的个数 - 最多存在 K - 1个不同整数的子区间的个数 = 恰好存在K个不同整数的子区间的个数。
三、代码
class Solution: def subarraysWithKDistinct(self, A: list, K: int) -> int: return self._subarrayWithDistinct(A, K) - self._subarrayWithDistinct(A, K - 1) # 计算最多为K的子数组长度 def _subarrayWithDistinct(self, A, K): freq_num = [0 for _ in range(len(A) + 1)] left, right = 0, 0 count = 0 res = 0 while right < len(A): if freq_num[A[right]] == 0: count += 1 freq_num[A[right]] += 1 right += 1 while count > K: freq_num[A[left]] -= 1 if freq_num[A[left]] == 0: count -= 1 left += 1 # 长度贡献 res += right - left return res if __name__ == '__main__': s = Solution() A = [1, 2, 1, 2, 3] K = 2 ans = s.subarraysWithKDistinct(A, K) print(ans)
到此,关于“leetcode怎么解决K 个不同整数的子数组”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
名称栏目:leetcode怎么解决K个不同整数的子数组
文章转载:http://scyanting.com/article/pdegeh.html