{"id":4835,"date":"2019-02-10T10:40:11","date_gmt":"2019-02-10T18:40:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4835"},"modified":"2019-02-10T10:42:53","modified_gmt":"2019-02-10T18:42:53","slug":"leetcode-992-subarrays-with-k-different-integers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-992-subarrays-with-k-different-integers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 992. Subarrays with K Different Integers"},"content":{"rendered":"\n

Given an array A<\/code> of positive integers, call a (contiguous, not necessarily distinct) subarray of A<\/code> good<\/em> if the number of different integers in that subarray is exactly K<\/code>.<\/p>\n\n\n\n

(For example, [1,2,3,1,2]<\/code> has 3<\/code> different integers: 1<\/code>, 2<\/code>, and 3<\/code>.)<\/p>\n\n\n\n

Return the number of good subarrays of A<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>A = [1,2,1,2,3], K = 2\nOutput: <\/strong>7\nExplanation: <\/strong>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].\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>A = [1,2,1,3,4], K = 3\nOutput: <\/strong>3\nExplanation: <\/strong>Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= A.length <= 20000<\/code><\/li>
  2. 1 <= A[i] <= A.length<\/code><\/li>
  3. 1 <= K <= A.length<\/code><\/li><\/ol>\n\n\n\n
    Solution: Two pointers + indirection<\/h2>\n\n\n\n
    Let f(x) denote the number of subarrays with x or less distinct numbers.
    ans = f(K) – f(K-1)
    It takes O(n) Time and O(n) Space to compute f(x)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\n\/\/ vector: 56 ms, 10.1 MB\n\/\/ Hashtable: 126 ms, 25 MB\nclass Solution {\npublic:\n  int subarraysWithKDistinct(vector& A, int K) {\n    \/\/ Returns the number of subarrays with k or less distinct numbers.\n    auto subarrys = [&A](int k) {\n      vector count(A.size() + 1);\n      int ans = 0;\n      int i = 0;\n      for (int j = 0; j < A.size(); ++j) {\n        if (count[A[j]]++ == 0) \n          --k;\n        while (k < 0)\n          if (--count[A[i++]] == 0) ++k;\n        ans += j - i + 1;\n      }\n      return ans;\n    };\n    return subarrys(K) - subarrys(K - 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Related Problems<\/strong><\/h2>\n\n\n\n