Day 20：1566. Detect Pattern of Length M Repeated K or More Times

今日题目

题目连结：1566. Detect Pattern of Length M Repeated K or More Times
题目主题：Array, Enumeration

昨天介绍了 Enumeration 的基本概念，今天会在练习一题以Enumeration 当主题的题目，建议还没看过 Enumeration 先回 Day 19：1534. Count Good Triplets 看看简单说说 Enumeration。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一组数字阵列，目的是要确认是否有长度为 m 的子阵列连续出现 k 次，这个连续出现是不会有重叠的状况。如果连续出现了 k 次以上，回传 True，若没有则回传 False。

约束：

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

范例1

输入: arr = [1,2,4,4,4,4], m = 1, k = 3
输出: true
解说: 范例输入了 m = 1 代表要找到长度为 1 的子阵列，而 k = 3 代表这个子阵列要重复出现 3 次以上才算True，这边可以看到 [4] 已经连续出现了 4 次，因此最後回true。

范例2

输入: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
输出: true
解说: 这边可以看到 [2, 1] 及 [1, 2] 都符合长度为 2 的子阵列也不重叠的重复出现 2 次，因此最後回传true。事实上，只要有一组 m 长度的子阵列连续出现 k 次以上，就可以下结论为true。

范例3

输入: arr = [1,2,1,2,1,3], m = 2, k = 3
输出: false
解说: 可以看到 [1, 2] 的子阵列只连续出现了两次，[2, 1] 也只连续出现了两次，[1, 3]只出现了一次，但目标是要连续出现 3 次才算，因此最後回false。

范例4

输入: arr = [1,2,3,1,2], m = 2, k = 2
输出: false
解说: 这个范例可以注意的是，[1, 2] 子阵列虽然出现了两次，但因为中间隔着 3，不符合连续出现这个条件，因此最後回传false。

范例5

输入: arr = [2,2,2,2], m = 2, k = 3
输出: false
解说: 这边可以解释，虽然子阵列长度为 2 的 [2, 2] 仔细算的话会出现 3 次，但因为是重叠的状况出现才会有 3 次，如果连续不重叠的话只出现 2 次，因此这个范例也是回传false。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

宣告一个times用来记录一个不重叠连续出现次数及一个nowIndex记录目前的位置。
另外在宣告一个tmpPattern用来记录目前长度为 m 的子阵列。
跑一个回圈，将所有长度为 m 的子阵列都走过一次：
- 若已经出现 times >= k 的状况直接结束回传true。
- 每次移动会从 nowIndex 往前移动 m 。
- 移动後确认目前长度为 m 的子阵列是否与先前纪录的相同。
  - 相同：times + 1。
  - 不相同：nowIndex回原本的位置往前一步，times重新计算，最後重新纪录一组新的长度为 m 的子阵列。

图解过程

范例：arr = [1, 2, 1, 2, 3, 1, 3], m = 2, k = 2

上图中，每一圈会用 +m 在移动，step2 是有重复出现的例子，移动後取得目前长度为 m 的子阵列，与tmpPattern确认是否有连续出现，有的话times会+1表示出现次数。

而 step3 ~ step5 是没有连续出现的例子，若发现子阵列不同会更新tmpPattern继续往下确认，times重新算。

最後长度为 m 的子阵列都走过一次，没有连续出现 k 次的子阵列，所以最後回传false。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        times = 1 #不重叠连续出现次数
        nowIndex = 0 #目前走到的位置
        tmpPattern = arr[nowIndex:nowIndex+m] #纪录目前长度为 m 的子阵列
        while nowIndex < (len(arr) - m):
            # 若不重叠连续出现 k 次或以上直接结束，代表以符合条件
            if times >= k: break
            # 不重叠，因此每次移动直接移动 m 
            nowIndex += m
            if tmpPattern == arr[nowIndex:nowIndex+m]:
                # 若目前子阵列与纪录的子阵列相同，增加一次连续出现次数
                times += 1
            else:
                # 若不同，位置回到前一次的位置+1
                nowIndex -= m
                nowIndex += 1
                # 重新计算次数
                times = 1
                # 重新给一组新的长度为 m 的子阵列
                tmpPattern = arr[nowIndex:nowIndex+m]
        return times >= k