992. Subarrays with K Different Integers
Hard67.6% acceptance377,957 / 559,152 submissions
Asked by 17 companies
Topics
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]has3different integers:1,2, and3.
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 * 1041 <= nums[i], k <= nums.length
Hints
Hint 1
Try generating all possible subarrays and check for the number of unique integers. Increment the count accordingly.
Hint 2
How about using a map to store the count of integers?
Hint 3
Think about the Sliding Window and 2-pointer approach.
Similar Questions
Longest Substring Without Repeating CharactersMediumLongest Substring with At Most Two Distinct CharactersMediumLongest Substring with At Most K Distinct CharactersMediumCount Vowel Substrings of a StringEasyNumber of Unique Flavors After Sharing K CandiesMediumK Divisible Elements SubarraysMediumCount Complete Subarrays in an ArrayMedium