LeetCode992. Subarrays with K Different Integers

这篇具有很好参考价值的文章主要介绍了LeetCode992. Subarrays with K Different Integers。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length

二、题解

恰好有k个不同元素的子数组的个数 = 最多有k个不同元素的子数组的个数 - 最多有k-1个不同元素的子数组的个数文章来源地址https://www.toymoban.com/news/detail-807959.html

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return subarraysWithMostKDistinct(nums,k) - subarraysWithMostKDistinct(nums,k-1);
    }
    int subarraysWithMostKDistinct(vector<int>& nums,int k){
        unordered_map<int,int> map;
        int res = 0,collect = 0;
        for(int l = 0,r = 0;r < nums.size();r++){
            if(++map[nums[r]] == 1) collect++;
            while(collect > k){
                if(--map[nums[l++]] == 0) collect--;
            }
            res += r - l + 1;
        }
        return res;
    }
};

到了这里,关于LeetCode992. Subarrays with K Different Integers的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode 357. Count Numbers with Unique Digits

    Given an integer n, return the count of all numbers with unique digits, x, where 0 = x 1 0 n 0 = x 10^n 0 = x 1 0 n . f(0) = 1 f(1) = 10 f(k) = 9 * 9 * 8 * … * (9 - k + 2)

    2024年02月19日
    浏览(45)
  • LeetCode //C - 528. Random Pick with Weight

    You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i t h i^{th} i t h index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w). For example, if w = [1, 3], the probability of

    2024年04月22日
    浏览(27)
  • LeetCode2085. Count Common Words With One Occurrence

    Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays. Example 1: Input: words1 = [“leetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“leetcode”,“is”] Output: 2 Explanation: “leetcode” appears exactly once in each of the two arrays. We count this s

    2024年01月16日
    浏览(41)
  • LeetCode //C - 138. Copy List with Random Pointer

    A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer

    2024年02月11日
    浏览(34)
  • 【算法】Maximum Sum of Two Non-Overlapping Subarrays 两个非重叠子数组的最大和

    问题 有一个整数数组nums,和2个整数firstlen,secondlen,要求找出2个非重叠子数组中的元素的最大和,长度分别是firstlen,secondlen。 不限制2个子数组的先后顺序。 firstlen,secondlen的范围 [ 1 , 1000 ] [1,1000] [ 1 , 1000 ] firstlen+secondlen的范围 [ 2 , 1000 ] [2,1000] [ 2 , 1000 ] f i r s t l e n ,

    2023年04月27日
    浏览(121)
  • react的different算法

    React中的差异算法,也称为协调算法(Reconciliation Algorithm),是用于比较新旧虚拟DOM树并确定最小更新集合的一种策略。React的协调算法基于两个主要原则: 相同类型的组件生成相似的树形结构: 如果两个组件类型相同,则它们产生相似的树形结构。React会假设相同类型的组

    2024年02月22日
    浏览(39)
  • 【算法】Sum of Imbalance Numbers of All Subarrays 所有子数组中不平衡数字之和-进阶篇

    一个长度为 n 下标从 0 开始的整数数组 arr 的 不平衡数字 定义为,在 sarr = sorted(arr) 数组中,满足以下条件的下标数目: 0 = i n − 1 ,和 s a r r [ i + 1 ] − s a r r [ i ] 1 0 = i n - 1 ,和 sarr[i+1] - sarr[i] 1 0 = i n − 1 ,和 s a rr [ i + 1 ] − s a rr [ i ] 1 这里,sorted(arr) 表示将数组 arr 排序

    2024年02月13日
    浏览(53)
  • leetcode - 1293. Shortest Path in a Grid with Obstacles Elimination

    You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possib

    2024年02月08日
    浏览(43)
  • LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(41)
  • LeetCode 2441. Largest Positive Integer That Exists With Its Negative【哈希集合】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包