K Fərqli Tam Ədədli Alt Dizilər Leetcode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The K müxtəlif tam ədədləri olan alt sətirlər LeetCode Həlli – “K müxtəlif tam ədədləri olan alt massivlər” sizə ədədlərlə tam ədəd və k tam ədədi verildiyini bildirir. Biz ümumi sayını tapmalıyıq yaxşı alt massivlər ədədlərdən.

Yaxşı massiv ilə massiv müəyyən edilir dəqiq k fərqli tam ədədlər, alt massiv isə massivin bitişik hissəsi kimi müəyyən edilir.

Misal:

Input:  nums = [1,2,1,2,3], k = 2

Output: 7

Explanation:

• Cəmi 15 alt massiv var.
• Tam k fərqli tam ədədi olan alt sətirlər bunlardır: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2 ,XNUMX].

Input:  nums = [1,2,1,3,4], k = 3

Output: 3

Explanation:

• Tam 3 fərqli tam ədədi olan alt sətirlər bunlardır: [1,2,1,3], [2,1,3], [1,3,4].

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Hashmap və sürüşmə pəncərə texnikası.
2. Qoy S(k) ümumi sayı olsun alt massivlər ən çox k fərqli elementlə.
3. Sonra tapmaq lazımdır S(k) – S(k-1).
4. S(k) hesablamaq üçün istifadə edəcəyik sürüşmə pəncərəsi texnika lazımi sayda elementləri tapmaq üçün.
   1. Biz iki i və j göstəricisini saxlayacağıq və hər dəfə i irəli göstəricini 1 vahid artıracağıq.
   2. Həmçinin, hər bir irəli göstərici i üçün ən kiçik j indeksini tapmağa çalışacağıq ki, j<=i və [j, i] diapazonunda fərqli elementlərin sayı k-dan çox olmasın.
   3. i-nin hər bir mövqeyi üçün biz tələb olunan etibarlı alt massivləri əlavə edəcəyik i – j + 1 cavabımıza.
5. Cavabımızı S(k) – S(k-1) kimi qaytaracağıq.

Kodu

K müxtəlif tam ədədləri olan alt sətirlər Leetcode C++ Həlli:

class Solution {
public:
    int AtmostK(vector<int>& nums,int k){
        unordered_map<int,int> freq;
        int n = nums.size(),ans = 0,j = 0;
        for(int i=0;i<n;i++){
            freq[nums[i]]++;
            if(freq[nums[i]]==1){
                k--;
            }
            while(k<0){
                freq[nums[j]]--;
                if(!freq[nums[j]]){
                    k++;
                }
                j++;
            }
            ans += i - j + 1;
        }
        return ans;
    }
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int ans = AtmostK(nums,k) - AtmostK(nums,k-1);
        return ans;
    }
};

K müxtəlif tam ədədləri olan alt sətirlər Leetcode Java Həlli:

class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }
    int atMostK(int[] A, int K) {
        int i = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int j = 0; j < A.length; ++j) {
            if (count.getOrDefault(A[j], 0) == 0) K--;
            count.put(A[j], count.getOrDefault(A[j], 0) + 1);
            while (K < 0) {
                count.put(A[i], count.get(A[i]) - 1);
                if (count.get(A[i]) == 0) K++;
                i++;
            }
            res += j - i + 1;
        }
        return res;
    }
}

K Fərqli Tam Ədədli Alt Dizilər üçün Mürəkkəblik Təhlili Leetcode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütün massivi xətti vaxtda keçirik və yaxşı hash funksiyası O(1) vaxtında daxil etməyə və silməyə imkan verir, burada N = giriş massivinin ölçüsü. Biz həmçinin loqarifmik vaxtda daxil etməyə və silməyə imkan verən hashmapdan istifadə edə bilərik.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N) çünki həşmənin maksimum ölçüsü O(N) ola bilər.