Các phần mảng có đúng n phần tử khác nhau trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng arr làm đối số 1, số num làm đối số 2. Hàm đếm và trả về số mảng con chứa đúng num phần tử khác nhau.

Ví dụ, nếu đầu vào là:

const arr = [12, 15, 12, 15, 18]; 
const num = 2;

Thì đầu ra nên là:

const output = 7;

Giải thích đầu ra

Các mảng con có đúng 2 phần tử khác nhau:

[12,15], [15,12], [12,15], [15,18], [12,15,12], [15,12,15], [12,15,12,15]

Ví dụ minh họa

Mã thực hiện (sliding window + atMost(k) - atMost(k-1)):

const arr = [12, 15, 12, 15, 18]; 
const num = 2; 
const distinctSubarrays = (arr = [], num = 1) => { 
  const findDistinct = (count) => { 
    const map = {}; 
    let ptr = 0; 
    let distinct = 0; 
    let res = 0; 
    for(let right = 0; right < arr.length; right++){ 
      const num = arr[right]; 
      map[num] = (map[num] || 0) + 1; 
      if(map[num] === 1){ distinct += 1; }; 
      while(distinct > count){ 
        map[arr[ptr]] -= 1; 
        if(map[arr[ptr]] === 0){ distinct -= 1; }; 
        ptr += 1; 
      }; 
      res += right - ptr + 1; 
    }; 
    return res; 
  }; 
  return findDistinct(num) - findDistinct(num - 1); 
}; 
console.log(distinctSubarrays(arr, num));

Đầu ra

Kết quả trong console sẽ là:

7