Daily 30/03/2024: [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)

# 1. Tóm tắt đề bài
Cho một mảng số nguyên ```nums``` và một số nguyên ```k```, trả về số mảng con **tốt** của ```nums```.
Một mảng tốt là một mảng có số lượng các số nguyên khác nhau trong mảng đó chính xác là ```k```.

Ví dụ: [1,2,3,1,2] có 3 các số nguyên khác nhau: 1, 2 và 3.

#### Giới hạn
- $1 \le$ ```nums.length``` $\le 10^5$
- $1 \le$ ```nums[i], k``` $\le$ ```nums.length```

# 2. Tóm tắt lời giải

#### Phân tích
- Ban đầu khi giải bài toán này, mình đã bị nhầm, ở đây người ta yêu cầu số luọng số nguyên khác nhau chính xác là k. Trong khi đó chúng ta có thể giải quyết bằng kĩ thuật Sliding Window, chính xác hơn là dùng 2 con trỏ với bài toán đếm số mảng con có số nguyên khác nhau nhiều nhất là k. Hình như bài toán hôm qua, hôm kia tương tự như vậy thì phải.
- Tuy nhiên chúng ta có 1 nhận xét như sau, khi ta đếm được số mảng con có số nguyên khác nhau nhiều nhất là k , và số mảng con có số nguyên khác nhau nhiều nhất là k - 1. Thì hiệu của nó chính là số mảng con chính xác là k.
- Tất nhiên trường hợp chính xác là k cũng có cách tính một cách trực tiếp dùng 2 con trỏ luôn, tuy nhiên phần này sẽ dành cho bạn đọc.
# 3. Lời giải chi tiết

#### Code

class Solution:
    def slidingWindow(self, nums: List[int], k: int) -> int:
        n = len(nums)
        i,j = 0, 0
        count = 0
        mp = defaultdict(int)
        
        while j < n:
            mp[nums[j]] += 1
            
            while len(mp) > k:
                mp[nums[i]] -= 1
                if mp[nums[i]] == 0:
                    del mp[nums[i]]
                i += 1
            
            count += j - i + 1
            j += 1
        
        return count
    
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        return self.slidingWindow(nums, k) - self.slidingWindow(nums, k - 1)
        

#### Độ phức tạp
$O(n)$

# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần rất nhẹ nhàng.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Sliding Window, Pointers</span>