LC.P992[K个不同整数的子数组]

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int n;
    int[] nums;

    public int subarraysWithKDistinct(int[] nums, int k) {
        this.nums = nums;
        this.n = nums.length;
        int[] lower = new int[n], upper = new int[n];
        find(lower, k); // 找到距离当前位置i为右边界的满足k个不同字符的下标
        find(upper, k - 1); // 找到距离当前位置i为右边界的满足k - 1个不同字符的下标
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += upper[i] - lower[i];
        }
        return ans;
    }

    private void find(int[] arr, int k) {
        int[] cnt = new int[n + 1];
        for (int i = 0, j = 0, sum = 0; i < n; ++i) {
            int right = nums[i];
            if (cnt[right]++ == 0) ++sum;
            while (sum > k) {
                int left = nums[j++];
                if (--cnt[left] == 0) --sum;
            }
            arr[i] = j;
        }
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$