题目描述

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

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

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

样例

输入：arr = [1,2,4,4,4,4], m = 1, k = 3
输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。

输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
输出：true
解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。

算法1

(模拟) $O(n)$

C++ 代码

class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        for(int i=0;i<=(int)arr.size()-k*m;i++){
            int j, t;
            for(j=0;j<m;j++){
                t=k-1;
                while(t!=0&&arr[i+j]==arr[i+j+m*t])t--;
                if(t!=0)break;
            }
            if(j==m&&t==0)return true;
        }
        return false;
    }
};