Question

1852. 每个子数组的数字种类数

English Version

题目描述

给你一个整数数组 nums与一个整数 k，请你构造一个长度 n-k+1 的数组 ans，这个数组第i个元素 ans[i] 是每个长度为k的子数组 nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]]中数字的种类数。

返回这个数组 ans。

 

示例 1:

输入: nums = [1,2,3,2,2,1,3], k = 3
输出: [3,2,2,2,3]
解释：每个子数组的数字种类计算方法如下：
- nums[0:2] = [1,2,3] 所以 ans[0] = 3
- nums[1:3] = [2,3,2] 所以 ans[1] = 2
- nums[2:4] = [3,2,2] 所以 ans[2] = 2
- nums[3:5] = [2,2,1] 所以 ans[3] = 2
- nums[4:6] = [2,1,3] 所以 ans[4] = 3

示例 2:

输入: nums = [1,1,1,1,2,3,4], k = 4
输出: [1,2,3,4]
解释: 每个子数组的数字种类计算方法如下：
- nums[0:3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1:4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2:5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3:6] = [1,2,3,4] 所以 ans[3] = 4

 

提示:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

解法

方法一：滑动窗口 + 哈希表或数组

我们用一个哈希表或数组 $cnt$ 用户记录每个长度为 $k$ 的子数组中数字的出现次数。

接下来，我们首先遍历数组前 $k$ 个元素，记录每个元素出现的次数，并且更新数字种类数 $v$，遍历后，我们首先将 $v$ 加入答案数组。

然后，我们从下标 $k$ 继续遍历数组，每次遍历时，我们将当前元素的出现次数加一，并且将当前元素左边的元素的出现次数减一，如果减一后的出现次数为 $0$，则将其从哈希表或数组中删除，然后更新数字种类数 $v$，将其加入答案数组。

遍历结束后，我们返回答案数组。

时间复杂度 $O(n)$，空间复杂度 $O(n)$ 或 $O(M)$。其中 $n$ 是数组 $nums$ 的长度；而 $M$ 是数组 $nums$ 中的最大值，本题中 $M \le 10^5$。

class Solution:
  def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
    cnt = Counter(nums[:k])
    ans = [len(cnt)]
    for i in range(k, len(nums)):
      cnt[nums[i]] += 1
      cnt[nums[i - k]] -= 1
      if cnt[nums[i - k]] == 0:
        cnt.pop(nums[i - k])
      ans.append(len(cnt))
    return ans

class Solution {
  public int[] distinctNumbers(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int i = 0; i < k; ++i) {
      cnt.merge(nums[i], 1, Integer::sum);
    }
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    ans[0] = cnt.size();
    for (int i = k; i < n; ++i) {
      cnt.merge(nums[i], 1, Integer::sum);
      if (cnt.merge(nums[i - k], -1, Integer::sum) == 0) {
        cnt.remove(nums[i - k]);
      }
      ans[i - k + 1] = cnt.size();
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> distinctNumbers(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int i = 0; i < k; ++i) {
      ++cnt[nums[i]];
    }
    int n = nums.size();
    vector<int> ans;
    ans.push_back(cnt.size());
    for (int i = k; i < n; ++i) {
      ++cnt[nums[i]];
      if (--cnt[nums[i - k]] == 0) {
        cnt.erase(nums[i - k]);
      }
      ans.push_back(cnt.size());
    }
    return ans;
  }
};

func distinctNumbers(nums []int, k int) []int {
  cnt := map[int]int{}
  for _, x := range nums[:k] {
    cnt[x]++
  }
  ans := []int{len(cnt)}
  for i := k; i < len(nums); i++ {
    cnt[nums[i]]++
    cnt[nums[i-k]]--
    if cnt[nums[i-k]] == 0 {
      delete(cnt, nums[i-k])
    }
    ans = append(ans, len(cnt))
  }
  return ans
}

function distinctNumbers(nums: number[], k: number): number[] {
  const cnt: Map<number, number> = new Map();
  for (let i = 0; i < k; ++i) {
    cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
  }
  const ans: number[] = [cnt.size];
  for (let i = k; i < nums.length; ++i) {
    cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
    cnt.set(nums[i - k], cnt.get(nums[i - k])! - 1);
    if (cnt.get(nums[i - k]) === 0) {
      cnt.delete(nums[i - k]);
    }
    ans.push(cnt.size);
  }
  return ans;
}

方法二

class Solution {
  public int[] distinctNumbers(int[] nums, int k) {
    int m = 0;
    for (int x : nums) {
      m = Math.max(m, x);
    }
    int[] cnt = new int[m + 1];
    int v = 0;
    for (int i = 0; i < k; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++v;
      }
    }
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    ans[0] = v;
    for (int i = k; i < n; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++v;
      }
      if (--cnt[nums[i - k]] == 0) {
        --v;
      }
      ans[i - k + 1] = v;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> distinctNumbers(vector<int>& nums, int k) {
    int m = *max_element(begin(nums), end(nums));
    int cnt[m + 1];
    memset(cnt, 0, sizeof(cnt));
    int n = nums.size();
    int v = 0;
    vector<int> ans(n - k + 1);
    for (int i = 0; i < k; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++v;
      }
    }
    ans[0] = v;
    for (int i = k; i < n; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++v;
      }
      if (--cnt[nums[i - k]] == 0) {
        --v;
      }
      ans[i - k + 1] = v;
    }
    return ans;
  }
};

func distinctNumbers(nums []int, k int) (ans []int) {
  m := slices.Max(nums)
  cnt := make([]int, m+1)
  v := 0
  for _, x := range nums[:k] {
    cnt[x]++
    if cnt[x] == 1 {
      v++
    }
  }
  ans = append(ans, v)
  for i := k; i < len(nums); i++ {
    cnt[nums[i]]++
    if cnt[nums[i]] == 1 {
      v++
    }
    cnt[nums[i-k]]--
    if cnt[nums[i-k]] == 0 {
      v--
    }
    ans = append(ans, v)
  }
  return
}

function distinctNumbers(nums: number[], k: number): number[] {
  const m = Math.max(...nums);
  const cnt: number[] = Array(m + 1).fill(0);
  let v: number = 0;
  for (let i = 0; i < k; ++i) {
    if (++cnt[nums[i]] === 1) {
      v++;
    }
  }
  const ans: number[] = [v];
  for (let i = k; i < nums.length; ++i) {
    if (++cnt[nums[i]] === 1) {
      v++;
    }
    if (--cnt[nums[i - k]] === 0) {
      v--;
    }
    ans.push(v);
  }
  return ans;
}