K개의 다른 정수가 있는 부분배열 Leetcode 솔루션

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 구글 동네 짱
배열 계산 해싱 하자 넷픽스 슬라이딩 윈도우조회수 47

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 K개의 다른 정수가 있는 부분배열 LeetCode 솔루션 – "K개의 다른 정수가 있는 하위 배열"에서는 정수 배열 nums와 정수 k가 주어졌다고 말합니다. 총 개수를 구해야 합니다. 좋은 하위 배열 숫자의.

좋은 배열은 다음과 같은 배열로 정의됩니다. 정확히 k 고유한 정수인 반면 하위 배열은 배열의 연속적인 부분으로 정의됩니다.

예:

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

설명 :

  • 총 15개의 하위 배열이 있습니다.
  • 정확히 k개의 고유한 정수가 있는 하위 배열은 다음과 같습니다. [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

설명 :

  • 정확히 3개의 고유한 정수가 있는 하위 배열은 [1,2,1,3], [2,1,3], [1,3,4]입니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 해시 맵 슬라이딩 윈도우 기법.
  2. 하자 에스(k) 총 수 하위 배열 최대 k개의 개별 요소가 있습니다.
  3. 그런 다음 우리는 찾아야합니다. S(k) – S(k-1).
  4. S(k)를 계산하기 위해 다음을 사용합니다. 슬라이딩 윈도우 기술 필요한 요소 수를 찾습니다.
    1. 우리는 두 개의 포인터 i와 j를 유지하고 매번 앞으로 포인터 i를 1단위씩 증가시킬 것입니다.
    2. 또한 각 포워드 포인터 i에 대해 j<=i이고 범위 [j, i]의 개별 요소 수가 k보다 크지 않은 최소 인덱스 j를 찾으려고 시도합니다.
    3. i의 각 위치에 대해 필요한 유효한 하위 배열을 추가합니다. 나는 – j + 1 우리의 대답에.
  5. 답은 S(k) – S(k-1)로 반환합니다.

암호

K개의 다른 정수가 있는 하위 배열 Leetcode C++ 솔루션:

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개의 다른 정수가 있는 하위 배열 Leetcode Java 솔루션:

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개의 다른 정수를 사용한 부분배열에 대한 복잡성 분석 Leetcode 솔루션

시간 복잡성

위 코드의 시간 복잡성은 의 위에) 선형 시간에 전체 배열을 탐색하고 좋은 해시 함수는 O(1) 시간에 삽입 및 삭제를 허용하기 때문에 N = 입력 배열의 크기입니다. 로그 시간에 삽입 및 삭제를 허용하는 해시맵을 사용할 수도 있습니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. 의 위에) 해시맵의 최대 크기는 O(N)일 수 있기 때문입니다.

균열 시스템 설계 인터뷰
Translate »