class Solution {
public:
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
}
};
3036. 匹配模式数组的子数组数目 II
给你一个下标从 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原站题解
golang 解法, 执行用时: 193 ms, 内存消耗: 41.1 MB, 提交时间: 2024-02-19 10:42:38
// z函数
func countMatchingSubarrays2(nums, pattern []int) (ans int) {
m := len(pattern)
pattern = append(pattern, 2)
for i := 1; i < len(nums); i++ {
pattern = append(pattern, cmp.Compare(nums[i], nums[i-1]))
}
n := len(pattern)
z := make([]int, n)
l, r := 0, 0
for i := 1; i < n; i++ {
if i <= r {
z[i] = min(z[i-l], r-i+1)
}
for i+z[i] < n && pattern[z[i]] == pattern[i+z[i]] {
l, r = i, i+z[i]
z[i]++
}
}
for _, lcp := range z[m+1:] {
if lcp == m {
ans++
}
}
return
}
func countMatchingSubarrays(nums, pattern []int) (ans int) {
m := len(pattern)
pi := make([]int, m)
cnt := 0
for i := 1; i < m; i++ {
v := pattern[i]
for cnt > 0 && pattern[cnt] != v {
cnt = pi[cnt-1]
}
if pattern[cnt] == v {
cnt++
}
pi[i] = cnt
}
cnt = 0
for i := 1; i < len(nums); i++ {
v := cmp.Compare(nums[i], nums[i-1])
for cnt > 0 && pattern[cnt] != v {
cnt = pi[cnt-1]
}
if pattern[cnt] == v {
cnt++
}
if cnt == m {
ans++
cnt = pi[cnt-1]
}
}
return
}
python3 解法, 执行用时: 217 ms, 内存消耗: 58.9 MB, 提交时间: 2024-02-19 10:40:58
class Solution:
# kmp
def countMatchingSubarrays2(self, nums: List[int], pattern: List[int]) -> int:
m = len(pattern)
pattern.append(2)
pattern.extend((y > x) - (y < x) for x, y in pairwise(nums))
n = len(pattern)
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(z[i - l], r - i + 1)
while i + z[i] < n and pattern[z[i]] == pattern[i + z[i]]:
l, r = i, i + z[i]
z[i] += 1
return sum(lcp == m for lcp in z[m + 1:])
# z函数
def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
m = len(pattern)
pi = [0] * m
cnt = 0
for i in range(1, m):
v = pattern[i]
while cnt and pattern[cnt] != v:
cnt = pi[cnt - 1]
if pattern[cnt] == v:
cnt += 1
pi[i] = cnt
ans = cnt = 0
for x, y in pairwise(nums):
v = (y > x) - (y < x)
while cnt and pattern[cnt] != v:
cnt = pi[cnt - 1]
if pattern[cnt] == v:
cnt += 1
if cnt == m:
ans += 1
cnt = pi[cnt - 1]
return ans