跳转至

4033. 有效 K 个不同元素子数组 I

题目描述

给定一个整数数组 nums 和一个整数 k。

同时给定一个二维整数数组 queries，其中 queries[i] = [li, ri] 表示子数组 nums[li..ri]。

对于每个查询，如果子数组 nums[li..ri] 满足以下条件，则认为该 子数组 是 有效的：

  • 它 恰好 包含 k 个 不同 的数字，并且
  • 子数组中每个数字出现的 频率 都是 偶数。

返回一个布尔数组 ans，其中如果 nums[li..ri] 是 有效的，则 ans[i] 为 true，否则为 false。

 

示例 1：

输入： nums = [1,2,2,1], k = 2, queries = [[0,1],[0,3],[1,2]]

输出： [false,true,false]

解释：

i [li, ri] 子数组 不同的数字 频率 有效性检查
0 [0, 1] [1, 2] {1, 2} → 2 {1: 1, 2: 1} false：元素出现的次数不是偶数。
1 [0, 3] [1, 2, 2, 1] {1, 2} → 2 {1: 2, 2: 2} true：恰好有 k = 2 个不同的元素，并且所有元素出现的次数都是偶数。
2 [1, 2] [2, 2] {2} → 1 {2: 2} false：不同元素的数量小于 k = 2。

因此，ans = [false, true, false]。

示例 2：

输入： nums = [3,3,3], k = 1, queries = [[1,2],[0,2]]

输出： [true,false]

解释：

i [li, ri] 子数组 不同的数字 频率 有效性检查
0 [1, 2] [3, 3] {3} → 1 {3: 2} true：恰好有 k = 1 个不同的元素，并且该元素出现的次数为偶数。
1 [0, 2] [3, 3, 3] {3} → 1 {3: 3} false：数字 3 出现的次数不是偶数。

因此，ans = [true, false]。

 

提示：

  • 2 <= n == nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= n
  • 1 <= queries.length <= 105
  • queries[i] == [li, ri]
  • 0 <= li < ri <= n - 1

解法

方法一

思考

询问子数组是否恰好含 \(k\) 个不同值且每个值出现偶数次，\(n\) 与询问均为 \(10^5\)，不能每次再扫一遍区间。

频次全为偶数等价于区间内每个值的出现次数模 \(2\) 为 \(0\)，可用前缀异或哈希在 \(O(1)\) 判断；不同值个数则需要另一套前缀或分块信息。

两者结合后，每个询问可以在对数或接近常数的时间内回答。

1


1


1


1

评论