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

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 微软
标签
数组 枚举
目录

题目描述

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

题意分析

给定一个整数数组和两个参数 m、k，问数组中是否存在一段由某个长度为 m 的模式连续重复至少 k 次拼成的子数组。返回布尔值，不需要指出模式内容或位置。

三个词需要抠清楚。「连续」指这 k 次重复必须首尾相接、中间不能有别的元素。「至少 k 次」在实现上等价于「恰好 k 次」——如果某处重复了 k + 1 次，那它的前 k 次本身就构成一个合法答案，所以只要能找到长度恰为 m * k 的合法段就够了。「模式」没有额外要求，元素可以全相同，也就是说像 [1,1,1,1] 配 m = 1、k = 4 是成立的。

数组长度上限只有 100，m 和 k 也都不超过 100。这个规模非常宽松，暗示出题人接受一个把所有起点、所有位置都试一遍的直接做法，不需要任何字符串匹配的高级结构。

一个显然的剪枝条件是 m * k > n 时必然无解，因为连放下这么长的一段都做不到。

边界上要注意 k = 1 时任何长度不小于 m 的数组都成立（一个模式出现一次总是可以的），而 m * k 恰好等于 n 时唯一的候选起点是 0。

解法：窗口逐位比较

核心思路

长度为 m 的模式连续重复 k 次，当且仅当后 m*(k-1) 个位置都满足 arr[i] == arr[i-m]。每个位置与前一块的同位置相等，便能由传递性保证所有块一致。

因此从下标 m 开始扫描，维护 matched：它表示截至当前位置，连续满足 arr[i] == arr[i-m] 的比较次数。匹配就加一，不匹配就清零；一旦达到 m*(k-1)，对应的长度 m*k 区间就是答案。

不变量：处理完下标 i 后，matched 恰好是以 i 结尾的最长连续周期匹配段长度。达到目标值时，这些比较连同它们前面的首个模式块，恰好覆盖 k 个连续相同块。

正确性：若算法返回真，连续的每个位置都与前 m 位相等，逐块推出 k 块相同；若存在合法模式，它后 k-1 块的全部 m*(k-1) 次比较必然连续成功，扫描一定会返回真。

解题步骤

  1. 若 m*k > arr.length，直接返回 false。
  2. 目标连续匹配次数为 needed = m*(k-1)；needed == 0 时一个模式块自身就满足要求。
  3. 从 i=m 开始比较 arr[i] 与 arr[i-m]，匹配则递增 matched，否则清零。
  4. matched >= needed 时返回 true；扫描结束仍未达到则返回 false。

arr=[1,2,4,4,4,4]、m=1、k=3 时，从下标 3 开始连续两次与前 1 位相等，找到 [4,4,4]。

反例 arr=[1,2,1,2,1,3]、m=2、k=3 的最后一次比较是 3 != 2，连续匹配被打断，不能把前两块误判成三块。

代码实现

class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        if (m * k > arr.length) {
            return false;
        }
        if (k == 1) {
            return true;
        }
        int needed = m * (k - 1);
        int matched = 0;
        for (int i = m; i < arr.length; i++) {
            if (arr[i] == arr[i - m]) {
                matched++;
            } else {
                matched = 0;
            }
            if (matched >= needed) {
                return true;
            }
        }
        return false;
    }
}

func containsPattern(arr []int, m int, k int) bool {
	if m*k > len(arr) {
		return false
	}
	if k == 1 {
		return true
	}
	needed := m * (k - 1)
	matched := 0
	for i := m; i < len(arr); i++ {
		if arr[i] == arr[i-m] {
			matched++
		} else {
			matched = 0
		}
		if matched >= needed {
			return true
		}
	}
	return false
}

复杂度分析

  • 时间复杂度：$O(n)$，每个下标只比较一次。
  • 空间复杂度：$O(1)$。

关键点总结

  • 连续重复等价于固定周期 m 的逐位相等。
  • k 个块只需验证后 k-1 个块，共 m*(k-1) 次连续比较。
  • 不匹配时必须把连续计数清零，下一次匹配从新的候选窗口开始。
  • k=1 时只需确认数组能容纳一个长度为 m 的模式。

易错点总结

  • 把目标比较次数写成 m*k：会多要求一个模式块，合法窗口被漏掉。
  • 不匹配后不清零：两个分离的匹配片段可能被拼成一个不存在的连续模式。
  • 从 i=0 比较 arr[i-m]：会访问负下标；前 m 个元素是首块，无需比较。
  • 忽略长度剪枝：m*k > n 时不存在完整窗口。
  • k=1 仍等待一次匹配：单个模式无需与前一块比较，应直接成立。

相似题目

题目 难度 考察点
459. 重复的子字符串 简单 周期长度未知需要枚举因数，还有拼接串或 KMP 前缀函数的巧解
1668. 最大重复子字符串 简单 模式固定而重复次数未知，求的是最大重复次数而非存在性
28. 找出字符串中第一个匹配项的下标 简单 模式由外部给定，考的是朴素匹配与 KMP 的对比
187. 重复的DNA序列 中等 定长窗口配哈希去重，找的是不连续出现的重复而非连续周期
30. 串联所有单词的子串 困难 块的顺序任意，需要用计数表匹配而非逐位比较
796. 旋转字符串 简单 同样是周期与拼接的性质，判定靠「拼接后包含」这一等价转化
424. 替换后的最长重复字符 中等 窗口长度可变且允许若干次替换，需要滑动窗口维护出现次数最大值