113. Exactly K Kinds
A music app logs the track ids you played as the array nums. A session is any non-empty contiguous run of plays. The variety of a session is the number of different track ids in it; repeats of an id already heard in the session do not raise the variety.
Return how many sessions have a variety of exactly k. Sessions at different positions are counted separately even when their contents are identical. Because of the limit on n, the answer always fits in a 32-bit signed integer.
Example 1
- Input:
- nums = [5,6,5,7,6], k = 2
- Output:
- 5
- Explanation:
Five sessions have exactly two ids: [5,6], [6,5], [5,6,5], [5,7] and [7,6].
Example 2
- Input:
- nums = [4,4,4], k = 1
- Output:
- 6
- Explanation:
Every one of the six sessions contains only the id 4, so the answer is 6.
Example 3
- Input:
- nums = [1,2,3], k = 4
- Output:
- 0
- Explanation:
The log only contains three different ids, so no session reaches variety 4.
Constraints
1 ≤ nums.length ≤ 60000
1 ≤ nums[i], k ≤ nums.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)