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

🟠   🔖  字典树 数组 哈希表 枚举 哈希函数 滚动哈希  🔗 力扣 LeetCode

题目

Given an integer array nums and two integers k and p, return the number of distinct subarrays, which have at most k elements that are divisible by p.

Two arrays nums1 and nums2 are said to be distinct if:

• They are of different lengths, or
• There exists at least one index i where nums1[i] != nums2[i].

A subarray is defined as a non-empty contiguous sequence of elements in an array.

Example 1:

Input: nums = [ _ 2_ ,3,3, _ 2_ , _ 2_ ], k = 2, p = 2

Output: 11

Explanation:

The elements at indices 0, 3, and 4 are divisible by p = 2.

The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:

[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], and [2,2].

Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once.

The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 4, p = 1

Output: 10

Explanation:

All element of nums are divisible by p = 1.

Also, every subarray of nums will have at most 4 elements that are divisible by 1.

Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.

Constraints:

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

Follow up:

Can you solve this problem in O(n2) time complexity?

题目大意

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

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

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

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

进阶：

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

解题思路

• 可以用两次循环遍历数组，在循环中记录满足条件的子数组数；
• 用一个哈希 Set 来记录满足条件的不同子数组，一个哈希 Map 记录 nums 中的每个数是否能被 p 整除；
• 用变量 count 记录当前子数组中被 p 整除的元素个数，变量 temp 记录当前子数组；
• 在循环中记录满足条件的子数组数，然后返回即可；
• 注意 Set 中的数据是用 , 连接的字符串形式，否则会有 bug；

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} p
 * @return {number}
 */
var countDistinct = function (nums, k, p) {
	let res = new Set(), // 记录满足条件的不同子数组
		map = new Map(); // 记录 nums 中的每个数是否能被 p 整除

	for (let i = 0; i < nums.length; i++) {
		let count = 0, // 记录当前子数组中被 p 整除的元素个数
			temp = []; // 记录当前子数组

		for (let j = i; j < nums.length; j++) {
			if (!map.has(j)) {
				map.set(j, nums[j] % p == 0);
			}
			if (map.get(j)) {
				count++;
			}
			if (count <= k) {
				temp.push(nums[j]);
				res.add(temp.join(','));
			} else {
				break;
			}
		}
	}
	return res.size;
};

相关题目

题号	标题	题解	标签	难度
992	K 个不同整数的子数组		数组 哈希表 计数 1+
1248	统计「优美子数组」		数组 哈希表 数学 2+
2334	元素值大于变化阈值的子数组		栈 并查集 数组 1+