ซับอาร์เรย์ที่มีจำนวนจำนวนเต็มต่างกัน K ตัวใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ของจำนวนเต็มบวก ซับอาร์เรย์ "ดี" คือซับอาร์เรย์ติดต่อกันที่มีจำนวนจำนวนเต็มที่ต่างกันพอดี K ตัว หาจำนวนซับอาร์เรย์ที่ดี

ตัวอย่าง

A = [1,2,3,1,4], K = 3 → Output: 4
ซับอาร์เรย์: [1,2,3], [1,2,3,1], [2,3,1], [3,1,4]

แนวทางแก้ปัญหา: Sliding Window + AtMost(K) - AtMost(K-1)

จำนวนซับอาร์เรย์ที่มี distinct = K เท่ากับ (จำนวนที่ ≤ K) - (จำนวนที่ ≤ K-1)

ฟังก์ชัน atMost(k)

• Two pointers: left=j, right=i
• ขยายขวา: เพิ่ม A[i] เข้า frequency map
• ถ้าจำนวน distinct > k: หดซ้าย (j++) จน distinct ≤ k
• จำนวนซับอาร์เรย์ที่จบที่ i และ valid = i - j + 1
• สะสมคำตอบ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int atMost(vector<int>& a, int k) {
        if(k < 0) return 0;
        unordered_map<int,int> freq;
        int j = 0, ans = 0;
        for(int i=0; i