Easy

题目描述

给你一个正整数数组 arr，请你找到一个长度为 m 的模式，该模式重复 k 次或更多次。

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

如果存在长度为 m 且重复 k 次或更多次的模式，返回 true，否则返回 false。

示例 1：

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

示例 2：

输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
输出：true
解释：模式 (1,2) 长度为 2，连续重复 2 次。另一个有效模式 (2,1) 也重复了 2 次。

示例 3：

输入：arr = [1,2,1,2,1,3], m = 2, k = 3
输出：false
解释：模式 (1,2) 长度为 2，但只重复了 2 次。没有长度为 2 且重复 3 次或更多次的模式。

提示：

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

解题思路

这道题要求在数组中找到长度为 m 的模式重复 k 次或更多次。

思路分析：

  1. 暴力枚举法：遍历所有可能的起始位置，对每个位置尝试提取长度为 m 的模式，然后检查是否连续重复了 k 次或更多。

  2. 滑动窗口法：对于每个起始位置，使用双指针技术来检查模式的重复情况。

  3. 优化的连续计数法：遍历数组，对于每个位置检查从该位置开始是否存在连续重复的模式。

推荐解法：暴力枚举法

具体步骤：

  • 遍历所有可能的起始位置 i（从 0 到 n - m*k）
  • 对于每个起始位置，提取长度为 m 的模式
  • 检查从位置 i + m 开始，该模式是否连续重复了 k-1 次或更多
  • 使用计数器记录连续重复次数，如果达到 k 则返回 true

这种方法虽然是暴力解法，但由于数组长度限制在 100 以内，时间复杂度完全可以接受。

代码实现

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

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        n = len(arr)
        for i in range(n - m * k + 1):
            count = 1
            j = i + m
            while j <= n - m:
                if arr[i:i+m] == arr[j:j+m]:
                    count += 1
                    if count >= k:
                        return True
                    j += m
                else:
                    break
        return False

public class Solution {
    public bool ContainsPattern(int[] arr, int m, int k) {
        int n = arr.Length;
        for (int i = 0; i <= n - m * k; i++) {
            int count = 1;
            for (int j = i + m; j <= n - m; j += m) {
                bool match = true;
                for (int p = 0; p < m; p++) {
                    if (arr[i + p] != arr[j + p]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    count++;
                    if (count >= k) return true;
                } else {
                    break;
                }
            }
        }
        return false;
    }
}

var containsPattern = function(arr, m, k) {
    const n = arr.length;
    for (let i = 0; i <= n - m * k; i++) {
        let count = 1;
        for (let j = i + m; j <= n - m; j += m) {
            let match = true;
            for (let p = 0; p < m; p++) {
                if (arr[i + p] !== arr[j + p]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                count++;
                if (count >= k) return true;
            } else {
                break;
            }
        }
    }
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m × k)，其中 n 是数组长度。最坏情况下需要遍历所有起始位置，对每个位置检查 k 个长度为 m 的模式
空间复杂度O(1)，只使用了常数额外空间

相关题目