992. Subarrays with K Different Integers

LeetCode hard оригинал: C# #array #backtracking #csharp #hard #hash-table #leetcode #two-pointers

LeetCode Static

Дан целочисленный массив nums и целое число k, верните количество "хороших" подмассивов в nums.

"Хороший" массив - это массив, в котором количество различных целых чисел равно k.

Например, в массиве [1,2,3,1,2] есть 3 различных целых числа: 1, 2 и 3.

Подмассив - это непрерывная часть массива.

Пример

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

Output: 7

Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

C# решение

сопоставлено/оригинал

public class Solution {
    public int CountGoodSubarrays(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int right = 0;
        int distinctCount = 0;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        while (right < nums.Length) {
            if (!freq.ContainsKey(nums[right])) {
                freq[nums[right]] = 0;
            }
            freq[nums[right]]++;
            if (freq[nums[right]] == 1) {
                distinctCount++;
            }
            right++;
            
            while (distinctCount > k) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctCount--;
                }
                left++;
            }
            
            if (distinctCount == k) {
                count++;
            }
        }
        
        return count;
    }
}

C++ решение

auto-draft, проверить перед отправкой

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountGoodSubarrays(vector<int>& nums, int k) {
        int count = 0;
        int left = 0;
        int right = 0;
        int distinctCount = 0;
        unordered_map<int, int> freq = new unordered_map<int, int>();
        
        while (right < nums.size()) {
            if (!freq.count(nums[right])) {
                freq[nums[right]] = 0;
            }
            freq[nums[right]]++;
            if (freq[nums[right]] == 1) {
                distinctCount++;
            }
            right++;
            
            while (distinctCount > k) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctCount--;
                }
                left++;
            }
            
            if (distinctCount == k) {
                count++;
            }
        }
        
        return count;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int CountGoodSubarrays(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int right = 0;
        int distinctCount = 0;
        HashMap<int, int> freq = new HashMap<int, int>();
        
        while (right < nums.length) {
            if (!freq.containsKey(nums[right])) {
                freq[nums[right]] = 0;
            }
            freq[nums[right]]++;
            if (freq[nums[right]] == 1) {
                distinctCount++;
            }
            right++;
            
            while (distinctCount > k) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctCount--;
                }
                left++;
            }
            
            if (distinctCount == k) {
                count++;
            }
        }
        
        return count;
    }
}

JavaScript решение

сопоставлено/оригинал

var countGoodSubarrays = function(nums, k) {
    let count = 0;
    let left = 0;
    let right = 0;
    let distinctCount = 0;
    const freq = new Map();
    
    while (right < nums.length) {
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        if (freq.get(nums[right]) === 1) {
            distinctCount++;
        }
        right++;
        
        while (distinctCount > k) {
            freq.set(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) === 0) {
                distinctCount--;
            }
            left++;
        }
        
        if (distinctCount === k) {
            count++;
        }
    }
    
    return count;
};

Python решение

сопоставлено/оригинал

class Solution:
    def countGoodSubarrays(self, nums: List[int], k: int) -> int:
        count = 0
        left = 0
        right = 0
        distinct_count = 0
        freq = {}
        
        while right < len(nums):
            freq[nums[right]] = freq.get(nums[right], 0) + 1
            if freq[nums[right]] == 1:
                distinct_count += 1
            right += 1
            
            while distinct_count > k:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    distinct_count -= 1
                left += 1
            
            if distinct_count == k:
                count += 1
                
        return count

Go решение

сопоставлено/оригинал

func countGoodSubarrays(nums []int, k int) int {
    count := 0
    left := 0
    right := 0
    distinctCount := 0
    freq := make(map[int]int)
    
    for right < len(nums) {
        freq[nums[right]]++
        if freq[nums[right]] == 1 {
            distinctCount++
        }
        right++
        
        for distinctCount > k {
            freq[nums[left]]--
            if freq[nums[left]] == 0 {
                distinctCount--
            }
            left++
        }
        
        if distinctCount == k {
            count++
        }
    }
    
    return count
}

Algorithm

Подсчет подмассивов с различными элементами:

Используйте два указателя для определения границ текущего подмассива.

Используйте хэш-таблицу для подсчета количества различных элементов в текущем подмассиве.

Перемещайте правый указатель для расширения подмассива и добавления новых элементов.

Проверка условий:

Как только количество различных элементов достигнет k, перемещайте левый указатель, чтобы уменьшить размер подмассива и попытаться найти все возможные "хорошие" подмассивы.

Подсчитывайте количество подмассивов, удовлетворяющих условию.

Возврат результата:

Верните общее количество "хороших" подмассивов.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.