1566. 重复至少 K 次且长度为 M 的模式

🟢   🔖  数组 枚举  🔗 力扣 LeetCode

题目

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated kor more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3

Output: true

Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2

Output: true

Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3

Output: false

Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Constraints:

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

题目大意

给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。

模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。

如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。

示例 1：

输入： arr = [1,2,4,4,4,4], m = 1, k = 3

输出： true

解释： 模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。

示例 2：

输入： arr = [1,2,1,2,1,1,1,3], m = 2, k = 2

输出： true

解释： 模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。

示例 3：

输入： arr = [1,2,1,2,1,3], m = 2, k = 3

输出： false

解释： 模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。

示例 4：

输入： arr = [1,2,3,1,2], m = 2, k = 2

输出： false

解释： 模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。

示例 5：

输入： arr = [2,2,2,2], m = 2, k = 3

输出： false

解释： 长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。

提示：

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

解题思路

1. 题目要求在数组中找到一个长度为 m 的模式，该模式连续重复至少 k 次。

2. 假设符合要求的模式为 arr[i, i+1, ..., i+m-1]，需要验证连续字符串 arr[i, i+1, ..., i + m * k - 1] 是否构成该模式的连续 k 次重复。

3. 定义计数器 count，用于记录匹配当前模式的连续元素长度，初始化为 m。

4. 遍历数组时，比较当前元素 arr[i] 和相隔 m 的元素 arr[i+m]：

   • 如果相等，说明模式连续有效，计数器加 1。
   • 如果不相等，说明模式中断，计数器重置为 m。

5. 当计数器达到 m * k 时，表示模式已重复至少 k 次，返回 true。

6. 如果遍历完整个数组仍未找到符合条件的模式，返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次。
• 空间复杂度：O(1)，使用了常数个变量。

代码

/**
 * @param {number[]} arr
 * @param {number} m
 * @param {number} k
 * @return {boolean}
 */
var containsPattern = function (arr, m, k) {
	let count = m;
	for (let i = 0; i <= arr.length - m; i++) {
		if (arr[i] == arr[i + m]) {
			count++;
			if (count == m * k) {
				return true;
			}
		} else {
			count = m;
		}
	}
	return false;
};

相关题目

题号	标题	题解	标签	难度	力扣
1668	最大重复子字符串	[✓]	字符串 动态规划 字符串匹配	🟢	🀄️ 🔗