class Solution {
public:
int countDistinct(vector<int>& nums, int k, int p) {
}
};
2261. 含最多 K 个可整除元素的子数组
给你一个整数数组 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 <= 2001 <= nums[i], p <= 2001 <= k <= nums.length原站题解
python3 解法, 执行用时: 452 ms, 内存消耗: 30 MB, 提交时间: 2023-05-05 17:15:06
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)
golang 解法, 执行用时: 384 ms, 内存消耗: 81.3 MB, 提交时间: 2023-05-05 17:14:52
func countDistinct(nums []int, k, p int) int {
set := map[[200]int]struct{}{}
for i := range nums {
arr, idx, cnt := [200]int{}, 0, 0
for _, v := range nums[i:] { // 从 i 开始向右扩展子数组
if v%p == 0 {
if cnt++; cnt > k {
break
}
}
arr[idx] = v
idx++
set[arr] = struct{}{}
}
}
return len(set)
}
python3 解法, 执行用时: 644 ms, 内存消耗: 30.6 MB, 提交时间: 2023-05-05 17:14:31
# 哈希表模拟
class Solution:
def countDistinct(self, nums: List[int], k: int, p: int) -> int:
s, n = set(), len(nums)
for i in range(n):
cnt = 0
for j in range(i, n):
if nums[j] % p == 0:
cnt += 1
if cnt > k:
break
s.add(tuple(nums[i: j + 1]))
return len(s)