Solution
Approach 1: Sliding Window
Intuition
For convenience, let's denote subarrays by tuples: (i,j) = [A[i], A[i+1], ..., A[j]]
, and call a subarray valid if it has K
different integers.
For each j
, let's consider the set of all i
such that the subarray (i, j)
is valid.
Firstly, must be a contiguous interval. If i1 < i2 < i3
, (i1,j)
and (i3,j)
are valid, but (i2,j)
is not valid, this is a contradiction because (i2,j)
must contain more than K
different elements [as (i3,j)
contains K
], but (i1,j)
[which is a superset of (i2,j)
] only contains K
different integers.
So now let's write as intervals: .
The second observation is that the endpoints of these intervals must be monotone increeasing  namely, and are monotone increasing. With similar logic to the above, we could construct a proof of this fact, but the intuition is that after adding an extra element to our subarrays, they are already valid, or we need to shrink them a bit to keep them valid.
Algorithm
We'll maintain two sliding windows, corresponding to and . Each sliding window will be able to count how many different elements there are in the window, and add and remove elements in a queuelike fashion.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.