LeetCode 题解工作台
匹配模式数组的子数组数目 I
给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ， pattern 数组只包含整数 -1 ， 0 和 1 。 大小为 m + 1 的 子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·rolling·哈希
答案摘要
我们可以枚举数组 `nums` 的所有长度为 $m + 1$ 的子数组，然后判断是否满足模式数组 `pattern`，如果满足则答案加一。 时间复杂度 $O(n \times m)$，其中 和 分别是数组 `nums` 和 `pattern` 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·rolling·哈希 题型思路
题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ，pattern 数组只包含整数 -1 ，0 和 1 。
大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式数组 pattern ：
- 如果
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 <= 1001 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1
解题思路
方法一：枚举
我们可以枚举数组 nums 的所有长度为 的子数组，然后判断是否满足模式数组 pattern，如果满足则答案加一。
时间复杂度 ，其中 和 分别是数组 nums 和 pattern 的长度。空间复杂度 。
class Solution:
def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
def f(a: int, b: int) -> int:
return 0 if a == b else (1 if a < b else -1)
ans = 0
for i in range(len(nums) - len(pattern)):
ans += all(
f(nums[i + k], nums[i + k + 1]) == p for k, p in enumerate(pattern)
)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*m) for direct comparison, reduced to O(n) using rolling hash. Space complexity is O(1) extra for counters and O(m) for hash storage of the pattern. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for subarrays matching a sequence of relative comparisons, not exact values.
- question_mark
Hinting to consider pattern length and efficient checking, possibly via rolling hash.
- question_mark
Expect awareness of off-by-one errors when indexing subarrays.
常见陷阱
外企场景- error
Forgetting that subarray length is pattern length plus one, leading to index errors.
- error
Comparing values directly without considering the sign mapping of pattern elements.
- error
Failing to update rolling hash correctly when sliding the window.
进阶变体
外企场景- arrow_right_alt
Pattern may include only increasing or decreasing sequences, simplifying checks.
- arrow_right_alt
Array elements could be negative or larger ranges, requiring hash adjustments.
- arrow_right_alt
Pattern length varies, affecting performance and hash collision probability.