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

题目

给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。

示例：

  1. 输入：arr = [1,2,4,4,4,4], m = 1, k = 3
  2. 输出：true
  3. 解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。
  1. 输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
  2. 输出：true
  3. 解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。
  1. 输入：arr = [1,2,1,2,1,3], m = 2, k = 3
  2. 输出：false
  3. 解释：模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。
  1. 输入：arr = [1,2,3,1,2], m = 2, k = 2
  2. 输出：false
  3. 解释：模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。
  1. 输入：arr = [2,2,2,2], m = 2, k = 3
  2. 输出：false
  3. 解释：长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。

解答 & 代码

遍历数组的每个位置 start（start∈[0, len - m * k]，否则长度不满足），作为模式的起点

  • 遍历偏移量 offset ∈ [0, m * k]，
    • 判断是否满足 arr[start + offset] == arr[start + offset % m]

  • 如果全都满足，则说明存在这样的模式，直接返回 true；否则继续遍历 start

    1. class Solution {
    2. public:
    3.   bool containsPattern(vector<int>& arr, int m, int k) {
    4.       int len = arr.size();
    5.       for(int start = 0; start <= len - m * k; ++start)    // 尝试以每个位置作为模式的起点
    6.       {
    7.           int offset = 0;
    8.           for(; offset < m * k; ++ offset)    // 遍历当前模式串的每一位，判断是否满足条件
    9.           {
    10.               if(arr[start + offset] != arr[start + offset % m])
    11.                   break;
    12.           }
    13.           if(offset == m * k)        //找到一个重复 k 次且长为 m 的模式，直接返回 true
    14.               return true;
    15.       }
    16.       return false;
    17.   }
    18. };

    复杂度分析：设数组 arr 长为 n，寻找长为 m 连续重复 k 次的模式

  • 时间复杂度 O(n m k)：两重循环，外层循环复杂度 O(n)，内层循环复杂度 O(m * k)

  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：7.9 MB, 在所有 C++ 提交中击败了 65.64% 的用户