Sliding Window Logical Thinking
so-called sliding window technique needs an aggregated requirement, for example, the window with at most K dinstinct or with at least K dinstinct.\n\n> so we tr
> so-called sliding window technique needs an aggregated requirement, for example, the window with at most K dinstinct or with at least K dinstinct.\n\n> so we transform the original problem to\n> ```\n>subarraysWith(K)Distinct = subarraysWithAtMost(K)Distinct - subarraysWithAtMost(K -1)Distinct\n>```\n\n> intuitively,\n> ```\n> for (i = 0, i < n; i++) {\n>   for (j = i; j < n; j++) {\n>     if ([i, j] with at most K distinct) numSubarrayAtMostKDistinct++;\n>   }\n> }\n> ```\n> optimize 1, loop j break earlier\n> ```\n> for (i = 0, i < n; i++) {\n>   for (j = i; j < n; j++) {\n>     if ([i, j] with at most K distinct) numSubarrayAtMostKDistinct++;\n>     else break;\n>   }\n> }\n> ```\n> optimize 2, j doen\'t restart at i but keeps increasing\n> ```\n> for (i = 0, i < n; i++) {\n>   for (; j < n; j++) {\n>     if ([i, j] with at most K distinct) numSubarrayAtMostKDistinct= j - i + 1;\n>     else break;\n>   }\n> }\n> ```\n\n> to check whether `[i, j] with at most K distinct`\n> we maintain a map `chToFreq` to record a digit and its corresponding frequency in curret window [i, j]\n****\n```\n    public int subarraysWithKDistinct(int[] A, int K) {\n        return subarraysWithAtMostKDistinct(A, K) - subarraysWithAtMostKDistinct(A, K - 1);\n    }\n    \n    private int subarraysWithAtMostKDistinct(int[] A, int K) {\n        if (K == 0) return 0;\n        \n        int j = 0, numGoodSubArr = 0, n = A.length;\n        // Map a character to its frequency in current window.\n        Map<Integer, Integer> chToFreq = new HashMap<>();\n        \n        for (int i = 0; i < n; i++) {\n            for (; j < n; j++) {\n                chToFreq.put(A[j], chToFreq.getOrDefault(A[j], 0) + 1);\n                if (chToFreq.size() <= K) numGoodSubArr += j - i + 1; \n                else {\n                    chToFreq.put(A[j], chToFreq.get(A[j]) - 1);\n                    if (chToFreq.get(A[j]) == 0) chToFreq.remove(A[j]);\n                    break; \n                }\n            }\n            chToFreq.put(A[i], chToFreq.get(A[i]) - 1);\n            if (chToFreq.get(A[i]) == 0) chToFreq.remove(A[i]);\n        }\n\n        return numGoodSubArr;\n    }\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
['Sliding Window']