---

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

• 标签：数组、枚举
• 难度：简单

题目链接

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

题目大意

描述：给定一个正整数数组 $arr$，以及两个整数 $m$ 和 $k$。

要求：判断是否存在长度为 $m$ 的连续子数组（模式）连续重复至少 $k$ 次。

说明：

• $2 \le arr.length \le 100$。
• $1 \le arr[i] \le 100$。
• $1 \le m \le 100$。
• $2 \le k \le 100$。
• 模式允许重叠吗？不允许，必须严格连续且不重叠的重复。

示例：

• 示例 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 次。

解题思路

思路 1：枚举起点

1. 核心思想

枚举每个可能的模式起点 $i$（$0 \le i \le n - m \times k$），检查从 $i$ 开始，每 $m$ 个元素是否与之前 $m$ 个元素完全相同。

2. 具体步骤

第 1 步：遍历 $i$ 从 $0$ 到 $n - m \times k$。

第 2 步：对于每个 $i$，检查后续连续 $k-1$ 个长度为 $m$ 的块是否与第 $1$ 个块完全相同。

第 3 步：如果找到满足条件的 $i$，返回 True。

第 4 步：遍历结束未找到，返回 False。

3. 举例说明

以 $arr = [1,2,1,2,1,2,1,2], m = 2, k = 3$ 为例：

• $i=0$：模式 $[1,2]$，检查后续块：
  • $[1,2]$（位置 2-3）：匹配
  • $[1,2]$（位置 4-5）：匹配
  • 连续 3 块，返回 True。

以 $arr = [1,2,1,2,1,3], m = 2, k = 3$ 为例：

• $i=0$：模式 $[1,2]$，检查：
  • $[1,2]$（位置 2-3）：匹配
  • $[1,3]$（位置 4-5）：不匹配
• $i=1$：模式 $[2,1]$，$n - m*k = 6 - 6 = 0$，不满足长度要求。
• 返回 False。

思路 1：代码

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        n = len(arr)
        for i in range(n - m * k + 1):
            # 检查从 i 开始，连续 k 个长度为 m 的块是否相同
            match = True
            for j in range(m):
                base = arr[i + j]
                for t in range(1, k):
                    if arr[i + t * m + j] != base:
                        match = False
                        break
                if not match:
                    break
            if match:
                return True
        return False

思路 1：复杂度分析

• 时间复杂度：$O(n \times m \times k)$，但 $n \le 100$，$m, k \le 100$，总操作数最多 $10^6$。
• 空间复杂度：$O(1)$。