Hard

题目描述

给你一个大小为 n 的 0 下标 整数数组 nums ，以及一个大小为 m 的 0 下标 整数数组 pattern ，pattern 数组只包含整数 -1、0 和 1 。

大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式：

  • 如果 pattern[k] == 1 ，那么 nums[i + k + 1] > nums[i + k]
  • 如果 pattern[k] == 0 ，那么 nums[i + k + 1] == nums[i + k]
  • 如果 pattern[k] == -1 ，那么 nums[i + k + 1] < nums[i + k]

请你返回匹配 pattern 的 nums 子数组数目。

示例 1：

输入：nums = [1,2,3,4,5,6], pattern = [1,1]
输出：4
解释：模式 [1,1] 说明我们要找的是长度为 3 的严格递增子数组。在数组 nums 中，子数组 [1,2,3] ，[2,3,4] ，[3,4,5] 和 [4,5,6] 都匹配这个模式。
因此，nums 中总共有 4 个子数组匹配这个模式。

示例 2：

输入：nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
输出：2
解释：这里，模式 [1,0,-1] 说明我们需要找的是这样的序列：第一个数字小于第二个，第二个等于第三个，第三个大于第四个。在数组 nums 中，子数组 [1,4,4,1] 和 [3,5,5,3] 都匹配这个模式。
因此，nums 中总共有 2 个子数组匹配这个模式。

提示：

  • 2 <= n == nums.length <= 10^6
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

解题思路

这道题的核心思想是将原问题转化为字符串匹配问题，然后使用高效的字符串匹配算法。

解题步骤：

  1. 数组转换：根据题目提示，我们首先构建一个新数组 nums2，其中：

    • 如果 nums[i+1] > nums[i]，则 nums2[i] = 1
    • 如果 nums[i+1] == nums[i]，则 nums2[i] = 0
    • 如果 nums[i+1] < nums[i]，则 nums2[i] = -1

  2. 问题转化：原问题转化为在 nums2 中查找有多少个子数组等于 pattern。这本质上是一个字符串匹配问题。

  3. 字符串匹配算法：由于数据规模较大（n 可达 10^6），我们需要使用高效的字符串匹配算法。常见的选择有：

    • KMP算法：时间复杂度 O(n+m)
    • Z算法：时间复杂度 O(n+m)
    • Rolling Hash：平均时间复杂度 O(n+m)

  4. 实现细节：这里我们使用KMP算法，它能够在线性时间内找到所有匹配位置。我们将 pattern 和 nums2 连接（中间用特殊分隔符），然后计算Z数组或失配函数来找到所有匹配。

推荐解法：使用KMP算法，因为它实现相对简单且性能稳定。

代码实现

class Solution {
public:
    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
        int n = nums.size();
        int m = pattern.size();
        
        // 构建nums2数组
        vector<int> nums2(n - 1);
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) nums2[i] = 1;
            else if (nums[i + 1] == nums[i]) nums2[i] = 0;
            else nums2[i] = -1;
        }
        
        // 使用KMP算法
        // 构建组合数组：pattern + 分隔符 + nums2
        vector<int> combined;
        for (int x : pattern) combined.push_back(x);
        combined.push_back(2); // 分隔符，不在{-1,0,1}中
        for (int x : nums2) combined.push_back(x);
        
        // 计算失配函数
        int len = combined.size();
        vector<int> lps(len, 0);
        for (int i = 1; i < len; i++) {
            int j = lps[i - 1];
            while (j > 0 && combined[i] != combined[j]) {
                j = lps[j - 1];
            }
            if (combined[i] == combined[j]) j++;
            lps[i] = j;
        }
        
        // 统计匹配数量
        int count = 0;
        for (int i = m + 1; i < len; i++) {
            if (lps[i] == m) count++;
        }
        
        return count;
    }
};

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        n = len(nums)
        m = len(pattern)
        
        # 构建nums2数组
        nums2 = []
        for i in range(n - 1):
            if nums[i + 1] > nums[i]:
                nums2.append(1)
            elif nums[i + 1] == nums[i]:
                nums2.append(0)
            else:
                nums2.append(-1)
        
        # 使用KMP算法
        # 构建组合数组：pattern + 分隔符 + nums2
        combined = pattern + [2] + nums2  # 2作为分隔符
        
        # 计算失配函数
        length = len(combined)
        lps = [0] * length
        for i in range(1, length):
            j = lps[i - 1]
            while j > 0 and combined[i] != combined[j]:
                j = lps[j - 1]
            if combined[i] == combined[j]:
                j += 1
            lps[i] = j
        
        # 统计匹配数量
        count = 0
        for i in range(m + 1, length):
            if lps[i] == m:
                count += 1
        
        return count

public class Solution {
    public int CountMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.Length;
        int m = pattern.Length;
        
        // 构建nums2数组
        int[] nums2 = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) nums2[i] = 1;
            else if (nums[i + 1] == nums[i]) nums2[i] = 0;
            else nums2[i] = -1;
        }
        
        // 使用KMP算法
        // 构建组合数组：pattern + 分隔符 + nums2
        List<int> combined = new List<int>();
        combined.AddRange(pattern);
        combined.Add(2); // 分隔符
        combined.AddRange(nums2);
        
        // 计算失配函数
        int len = combined.Count;
        int[] lps = new int[len];
        for (int i = 1; i < len; i++) {
            int j = lps[i - 1];
            while (j > 0 && combined[i] != combined[j]) {
                j = lps[j - 1];
            }
            if (combined[i] == combined[j]) j++;
            lps[i] = j;
        }
        
        // 统计匹配数量
        int count = 0;
        for (int i = m + 1; i < len; i++) {
            if (lps[i] == m) count++;
        }
        
        return count;
    }
}

var countMatchingSubarrays = function(nums, pattern) {
    const n = nums.length;
    const m = pattern.length;
    
    // 构建nums2数组
    const nums2 = [];
    for (let i = 0; i < n - 1; i++) {
        if (nums[i + 1] > nums[i]) nums2.push(1);
        else if (nums[i + 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)构建nums2数组需要O(n)，KMP算法需要O(n + m)
空间复杂度O(n + m)需要额外空间存储nums2、combined数组和lps数组

相关题目