LeetCode 1566. Repeat the pattern with length m at least k times

1566. Repeat at least K And the length is M The pattern of

Here's an array of positive integers arr, Please find a length of m And repeat at least... In the array k Second mode .

Pattern Is a subarray of one or more values （ Continuous subsequences ）, continuity Repeat many times, but No overlap . The pattern is defined by its length and number of repetitions .

If there are at least duplicates in the array k And the length is m The pattern of , Then return to true , Otherwise return to false .

Example 1：

 Input ：arr = [1,2,4,4,4,4], m = 1, k = 3
 Output ：true
 explain ： Pattern  (4)  The length of is  1 , And repeat continuously  4  Time . Be careful , Patterns can be repeated  k  Times or more , But not less than  k  Time .

Example 2：

 Input ：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
 Output ：true
 explain ： Pattern  (1,2)  The length is  2 , And repeat continuously  2  Time . Another pattern that fits the meaning of the question is  (2,1) , Same repetition  2  Time .

Example 3：

 Input ：arr = [1,2,1,2,1,3], m = 2, k = 3
 Output ：false
 explain ： Pattern  (1,2)  The length is  2 , But only repeat continuously  2  Time . There is no length of  2  And at least repeat  3  Second mode .

Example 4：

 Input ：arr = [1,2,3,1,2], m = 2, k = 2
 Output ：false
 explain ： Pattern  (1,2)  appear  2  Times but not continuously , So it can't be counted as continuous repetition  2  Time .

Example 5：

 Input ：arr = [2,2,2,2], m = 2, k = 3
 Output ：false
 explain ： The length is  2  The only mode is  (2,2) , But only repeat continuously  2  Time . Be careful , The number of overlapped repetitions cannot be calculated .

Tips ：

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

Two 、 Method 1

enumeration

class Solution {
    
    public boolean containsPattern(int[] arr, int m, int k) {
    
        int n = arr.length;
        for (int l = 0; l <= n - m * k; ++l) {
    
            int offset;
            for (offset = 0; offset < m * k; ++offset) {
    
                if (arr[l + offset] != arr[l + offset % m]) {
    
                    break;
                }
            }
            if (offset == m * k) {
    
                return true;
            }
        }
        return false;
    }
}

Complexity analysis

• Time complexity ：O(n×m×k). Outermost cycle l The number of values is n−m×k, Inner circulation offset The number of values is m×k, Therefore, the asymptotic time complexity is O((n−m×k)×m×k)=O(n×m×k).
• Spatial complexity ：O(1).