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

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

题目描述

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

image-20260929085307530

image-20260929085307622

题意分析

在数组任意位置，寻找长度为 m 的一段模式连续重复至少 k 次。相邻重复块首尾相接，不能重叠，也不能在块之间夹入其他元素；因此至少需要连续覆盖 m * k 个元素。

题目保证 k >= 2。模式的内容和起点都未知，但相邻两个重复块的对应元素一定相距 m，可以直接利用这个固定间隔比较。

解法：固定偏移的连续匹配

核心思路

[!blue]

从下标 m 开始，逐个比较 arr[i] 与 arr[i - m]。若某段由 k 个相同块组成，从第二块开始的每一个位置都应等于前一块的对应位置，共需要 m * (k - 1) 次连续成功比较。

反过来，如果连续这么多次比较都成功，那么这段比较连同前面的首块正好覆盖 m * k 个元素。每个位置都等于向前偏移 m 的位置，逐块传递后，全部 k 个块都等于首块，因此这个条件也足以证明模式存在。

用 matched 记录当前结尾连续成功的比较次数。相等就加一，不相等就清零；达到阈值立即返回 true。失配后重新累计，可以寻找从更后位置开始的模式，而无需预先枚举起点。

扫描步长是 1，不是 m，所以模式可以从任意下标开始。达到恰好 k 次重复已经满足“至少”的要求，不必继续查找是否还能扩展。

解题步骤

  1. 若 m * k 超过数组长度，直接返回 false。
  2. 令所需连续比较次数 needed = m * (k - 1)，当前次数 matched = 0。
  3. 从下标 m 开始逐位置比较相距 m 的两个元素：相等就增加 matched，失配就清零。
  4. 若 matched >= needed，当前结尾已经形成至少 k 个相同的非重叠块，返回 true。
  5. 扫描完成仍未达到阈值，返回 false。

代码实现

class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        if (m * k > arr.length) {
            return false;
        }

        // 首块之后还需连续匹配其余块的所有位置。
        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
    }
    // 首块之后还需连续匹配其余块的所有位置。
    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)$，只保存连续匹配次数。

关键点总结

[!green]

  • matched 统计连续成功的逐元素比较次数，既不是元素总数，也不是完整块数。
  • 第一块不需要与更早位置比较，因此只需检查后面 k - 1 块的所有位置。
  • 固定偏移负责保证块内容相同，比较结果的连续性负责保证重复块首尾相接。

易错点总结

[!yellow]

  • 失配必须清零，不能把中间断开的成功次数拼成一个重复模式。
  • 不能只从 m 的整数倍位置开始检查，合法起点不要求与数组开头对齐。
  • 阈值是 m * (k - 1)，写成 m * k 会额外要求一整块的比较。
  • 重复块不能重叠；数组总长度不足 m * k 时，即使含有相同值也不能满足要求。

相似题目

题目 难度 关联与区别
459. 重复的子字符串 简单 同样检测连续重复模式，原题要求覆盖整个字符串，本题寻找任意位置的固定长度重复块。
1668. 最大重复子字符串 简单 原题模式内容已知并求最大重复次数，本题只给模式长度并判断是否至少重复k次。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/41764540
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！