2261-含最多 K 个可整除元素的子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。

如果满足下述条件之一，则认为数组 nums1 和 nums2 是 不同 数组：

  • 两数组长度 不同 ，或者
  • 存在 至少 一个下标 i 满足 nums1[i] != nums2[i] 。

子数组 定义为：数组中的连续元素组成的一个 非空 序列。

示例 1：

**输入：** nums = [ _ **2**_ ,3,3, _ **2**_ , _ **2**_ ], k = 2, p = 2
**输出：** 11
**解释：**
位于下标 0、3 和 4 的元素都可以被 p = 2 整除。
共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素：
[2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。
注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。
子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。

示例 2：

**输入：** nums = [1,2,3,4], k = 4, p = 1
**输出：** 10
**解释：**
nums 中的所有元素都可以被 p = 1 整除。
此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。
因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length

进阶：

你可以设计并实现时间复杂度为 O(n2) 的算法解决此问题吗？

方法一：枚举 + 哈希集合去重

思路与算法

为了方便起见，我们可以首先考虑子数组不会重复出现的情况。

对于一个确定的整数数组 nums，它的子数组可以由左边界和右边界唯一决定。因此我们可以通过枚举左边界和右边界来遍历 nums 的所有子数组，并检查它们是否至多含 k 个可被 p 整除的元素。

具体地，我们用 res 来维护符合要求子数组的个数。我们首先枚举左边界 i，对于某个左边界 i，我们在枚举右边界 j 的同时用 cnt 统计子数组 nums}[i..j] （闭区间）中可被 p 整除的元素的个数。cnt 的初值为 0，如果 nums}[j] 可以被 p 整除，则我们将 cnt 加上 1。此时根据 cnt 和 k 的大小关系，有两种情况：

  • 如果此时 cnt} \le k，则说明子数组 nums}[i..j] 符合要求，我们将 res 加上 1，并继续枚举右边界；

  • 如果此时 cnt} > k，则说明子数组 nums}[i..j] 不符合要求，同时后续即将遍历到的满足 j_1 > j 的子数组 nums}[i..j_1] 由于包含 nums}[i..j] 显然也不符合要求，因此我们可以停止枚举右边界。

最终我们返回 res 作为答案即可。

随后我们考虑子数组会重复出现的情况。此时我们不能直接按照上文的方法统计个数，而需要对符合要求的子数组进行去重后计算。

我们可以用哈希集合来完成对应的去重操作。具体地，我们用哈希集合 arrs 来维护符合要求的子数组，按照与上文一致的遍历方法进行遍历，每当遍历到符合要求的子数组，我们将该子数组序列化（即通过一一映射转化为可哈希的元素）并放入哈希集合中。最终，我们返回 arrs 中的元素个数作为答案。

对于序列化的具体方式，对于 Python 等语言，我们可以将子数组转化为可哈希的元组放入哈希表；而对于 C++ 等语言，我们可以将子数组转化为字符串后放入哈希表。

具体地，我们用 s 表示序列化后的字符串。在每次开始遍历右边界前，我们初始化字符串。当遍历到对应下标时，我们将右边界对应的元素转化为字符串，并在末尾加上分隔符 `#‘ 后添加进 s 的尾部。可以证明，上述的序列化方式是一一映射。

代码

[sol1-C++]
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
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_set<string> arrs;   // 不同的（序列化后）子数组
        int n = nums.size();
        // 枚举左右边界
        for (int i = 0; i < n; ++i) {
            int cnt = 0;   // 当前被 p 整除的元素个数
            string s;   // 当前子数组序列胡后的字符串
            for (int j = i; j < n; ++j) {
                if (nums[j] % p == 0) {
                    ++cnt;
                    if (cnt > k) {
                        break;
                    }
                }
                // 序列化后放入哈希集合
                s.append(to_string(nums[j]));
                s.push_back('#');
                arrs.insert(s);
            }
        }
        return arrs.size();
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countDistinct(self, nums: List[int], k: int, p: int) -> int:
        arrs = set()   # 不同的（序列化后）子数组
        n = len(nums)
        # 枚举左右边界
        for i in range(n):
            cnt = 0   # 当前被 p 整除的元素个数
            arr = []   # 当前子数组
            for j in range(i, n):
                if nums[j] % p == 0:
                    cnt += 1
                    if cnt > k:
                        break
                arr.append(nums[j])
                # 序列化后放入哈希集合
                arrs.add(tuple(arr))
        return len(arrs)

复杂度分析

  • 时间复杂度：O(n^3)，其中 n 为数组 nums 的长度。我们共需遍历 O(n^2) 个子数组，序列化每个子数组并放入哈希集合的时间复杂度为 O(n)。

  • 空间复杂度：O(n^3)，即为哈希集合的空间开销。

 Comments
On this page
2261-含最多 K 个可整除元素的子数组