Medium

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个下标从 0 开始、长度为 m 的整数数组 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] 都匹配这个模式。
所以答案是 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] 都匹配这个模式。
所以答案是 2 。

提示：

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

解题思路

这道题要求找出数组中匹配给定模式的子数组数量。我们需要理解模式的含义：模式数组描述的是相邻元素之间的关系。

解题思路

方法一：暴力枚举（推荐）

由于数据规模较小（n ≤ 100），我们可以使用暴力枚举的方法：

  1. 遍历数组中所有可能的起始位置 i
  2. 对于每个起始位置，检查从该位置开始长度为 m+1 的子数组是否匹配模式
  3. 匹配条件：对于模式中的每个位置 k，检查 nums[i+k] 和 nums[i+k+1] 的关系是否符合 pattern[k] 的要求

方法二：字符串匹配优化

我们可以将数组转换为关系字符串，然后使用 KMP 算法进行匹配。首先将 nums 转换为相邻元素关系数组，再与 pattern 进行匹配。

由于题目数据规模小，暴力方法已经足够高效，代码也更容易理解和实现。

时间复杂度为 O(n×m)，其中 n 是 nums 的长度，m 是 pattern 的长度。

代码实现

class Solution {
public:
    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
        int n = nums.size();
        int m = pattern.size();
        int count = 0;
        
        // 遍历所有可能的起始位置
        for (int i = 0; i <= n - m - 1; i++) {
            bool matches = true;
            // 检查从位置i开始的子数组是否匹配模式
            for (int j = 0; j < m; j++) {
                int relation;
                if (nums[i + j + 1] > nums[i + j]) {
                    relation = 1;
                } else if (nums[i + j + 1] == nums[i + j]) {
                    relation = 0;
                } else {
                    relation = -1;
                }
                
                if (relation != pattern[j]) {
                    matches = false;
                    break;
                }
            }
            
            if (matches) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        n = len(nums)
        m = len(pattern)
        count = 0
        
        # 遍历所有可能的起始位置
        for i in range(n - m):
            matches = True
            # 检查从位置i开始的子数组是否匹配模式
            for j in range(m):
                if nums[i + j + 1] > nums[i + j]:
                    relation = 1
                elif nums[i + j + 1] == nums[i + j]:
                    relation = 0
                else:
                    relation = -1
                
                if relation != pattern[j]:
                    matches = False
                    break
            
            if matches:
                count += 1
        
        return count

public class Solution {
    public int CountMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.Length;
        int m = pattern.Length;
        int count = 0;
        
        // 遍历所有可能的起始位置
        for (int i = 0; i <= n - m - 1; i++) {
            bool matches = true;
            // 检查从位置i开始的子数组是否匹配模式
            for (int j = 0; j < m; j++) {
                int relation;
                if (nums[i + j + 1] > nums[i + j]) {
                    relation = 1;
                } else if (nums[i + j + 1] == nums[i + j]) {
                    relation = 0;
                } else {
                    relation = -1;
                }
                
                if (relation != pattern[j]) {
                    matches = false;
                    break;
                }
            }
            
            if (matches) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @param {number[]} pattern
 * @return {number}
 */
var countMatchingSubarrays = function(nums, pattern) {
    let count = 0;
    const n = nums.length;
    const m = pattern.length;
    
    for (let i = 0; i <= n - m - 1; i++) {
        let matches = true;
        
        for (let k = 0; k < m; k++) {
            const curr = nums[i + k];
            const next = nums[i + k + 1];
            
            if (pattern[k] === 1 && next <= curr) {
                matches = false;
                break;
            }
            if (pattern[k] === 0 && next !== curr) {
                matches = false;
                break;
            }
            if (pattern[k] === -1 && next >= curr) {
                matches = false;
                break;
            }
        }
        
        if (matches) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × m)
空间复杂度O(1)

其中 n 是 nums 数组的长度，m 是 pattern 数组的长度。在最坏情况下需要检查每个可能的起始位置，对于每个位置都要验证整个模式。

相关题目