Share my solution
Assume we have an array A = [1, 1, 2, 1, 1, 3, 3, 2, 4, 2] and K = 3\nLet\'s ask yourself how many ranges start with index = 0 and have 3 distinct numbers?\nWe 
Assume we have an array `A = [1, 1, 2, 1, 1, 3, 3, 2, 4, 2]` and `K = 3`\nLet\'s ask yourself how many ranges start with `index = 0` and have `3` distinct numbers?\nWe can at first find the first range that satisfies this condition using sliding window, in which keep one head `lo = 0`, and increase another head `hi = 0` until we count the distinct numbers `= 3`\n\n`[1]` - `lo = 0, hi = 0, count = 1`\n`[1,1]` - `lo = 0, hi = 1, count = 1`\n`[1,1,2]` - `lo = 0, hi = 2, count = 2`\n....\n`[1,1,2,1,1,3]` - `lo = 0, hi = 5, count = 3`\n\nOk. We found it. Now keep increasing `hi`, what will happen?\n\n`[1,1,2,1,1,3,3]` - `lo = 0, hi = 6, count still = 3`, because `A[hi] = 3` is still the one of the old numbers\n`[1,1,2,1,1,3,3,2]` - `lo = 0, hi = 7, count still = 3`, because `A[hi] = 2` is still the one of the old numbers\n**However**:\n`[1,1,2,1,1,3,3,2,4]` - `lo = 0, hi = 8, count = 4`, because `A[hi] = 4` is the new number\nSo, now we know if the new number appears, we can stop the journey. We call the `index` before making the new number appear is `max`. We have:\n\n- The range starting with `lo = 0` and have `K = 3` distinct numbers = `max - hi + 1`\n\n- The same analysis for how many ranges start with `lo = 1` and have `K = 3` distinct numbers = `max - hi + 1`\n- We keep shrinking the window by increasing `lo`, until the `count` of distinct numbers `< K = 3`. Then we repeat : increasing `hi` until the `count of distinct numbers `= `3`\n\n`1....1....2....1....1....3....3....2....4....2`\n`lo.......................hi........max`\n`...............lo.................hi=max`\n`.........................lo.............hi....max`\n\n````\n\tpublic int subarraysWithKDistinct(int[] A, int K) {\n        int res = 0, count = 0, lo = 0, hi = 0, max = 0, n;\n        Map<Integer, Integer> dp = new HashMap<>();\n\n        while (hi < A.length) {\n            \n            // define how many ranges starting with lo, and has K distinct numbers\n            while (count == K) {\n                res += max - hi + 1;\n                n = dp.get(A[lo]);\n                if (n == 1) {\n                    count--;\n                    hi++;\n                }\n                dp.put(A[lo], n-1);\n                lo++;\n            }\n\n            // find the first range starting with lo, and has K distinct numbers\n            while (hi < A.length) {\n                n = dp.getOrDefault(A[hi], 0);\n                if (n == 0) count++;\n                dp.put(A[hi], n+1);\n                \n                // if found hi, then define max\n                if (count == K) {\n                    max = hi;\n                    while (max+1 < A.length) {\n                        if (dp.getOrDefault(A[max+1], 0) == 0) break;\n                        max++;\n                    }\n                    break;\n                }\n                hi++;\n            }\n        }\n\n        return res;\n    }\n````
[]