LeetCode 题解工作台
匹配模式数组的子数组数目 II
给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ， pattern 数组只包含整数 -1 ， 0 和 1 。 大小为 m + 1 的 子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·结合·rolling·哈希
答案摘要
def partial(s): g, pi = 0, [0] * len(s)
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 <= 1061 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1
解题思路
方法一
def partial(s):
g, pi = 0, [0] * len(s)
for i in range(1, len(s)):
while g and (s[g] != s[i]):
g = pi[g - 1]
pi[i] = g = g + (s[g] == s[i])
return pi
def match(s, pat):
pi = partial(pat)
g, idx = 0, []
for i in range(len(s)):
while g and pat[g] != s[i]:
g = pi[g - 1]
g += pat[g] == s[i]
if g == len(pi):
idx.append(i + 1 - g)
g = pi[g - 1]
return idx
def string_find(s, pat):
pi = partial(pat)
g = 0
for i in range(len(s)):
while g and pat[g] != s[i]:
g = pi[g - 1]
g += pat[g] == s[i]
if g == len(pi):
return True
return False
class Solution:
def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
s = []
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
s.append(1)
elif nums[i] == nums[i - 1]:
s.append(0)
else:
s.append(-1)
return len(match(s, pattern))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to transform arrays efficiently.
- question_mark
Assesses understanding of rolling hash techniques for optimization.
- question_mark
Evaluates pattern matching skills and their application to subarrays.
常见陷阱
外企场景- error
Incorrectly transforming the array `nums` into `nums2` based on relative comparisons.
- error
Failure to optimize the solution with rolling hash, resulting in time complexity that is too high.
- error
Not accounting for edge cases, such as when `nums` has the smallest or largest possible length.
进阶变体
外企场景- arrow_right_alt
Using sliding window techniques instead of rolling hash for comparison.
- arrow_right_alt
Allowing for additional constraints in the pattern, such as different values for matching conditions.
- arrow_right_alt
Changing the input array structure, for example, making `nums` a list of strings instead of integers.