2024-07-06：用go语言，给定一个从0开始的长度为n的整数数组nums和一个从0开始的长度为m的整数数组pattern，其中pattern数组的元素只包含-1、0和1。

我们定义“匹配”的子数组，对于一个大小为m+1的子数组nums[i…j]，如果对于pattern数组中的每个元素pattern[k]都满足以下条件：

1.如果pattern[k]为1，则nums[i+k+1]必须大于nums[i+k]；

2.如果pattern[k]为0，则nums[i+k+1]必须等于nums[i+k]；

3.如果pattern[k]为-1，则nums[i+k+1]必须小于nums[i+k]。

要求计算有多少个子数组符合以上匹配条件。

输入：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 个子数组匹配这个模式。

答案2024-07-06：

chatgpt

题目来自leetcode3034。

大体步骤如下：

1.将 pattern 数组的长度记录为 m，接着为了方便处理，在 pattern 后面添加一个号码 2。

2.遍历 nums 数组，将 pattern 的内容替换为以 cmp.Compare 比较后得到的结果。

3.初始化一个结果变量 ans，用于存储匹配模式的子数组数量。

4.利用 Z 算法计算 pattern 的每个位置与后面的匹配长度。

5.遍历计算出的匹配长度数组，寻找长度为 m 且符合匹配模式的子数组。

6.返回最终匹配的子数组数量。

整体时间复杂度为 $O(n)$，其中 $n$ 为 nums 数组的长度。额外空间复杂度为 $O(n)$，用于存储额外的辅助信息。

Go完整代码如下：

package main

import (
	"fmt"
	"cmp"
)

func countMatchingSubarrays(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 main() {
	nums := []int{1, 2, 3, 4, 5, 6}
	pattern := []int{1, 1}
	fmt.Println(countMatchingSubarrays(nums, pattern))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def countMatchingSubarrays(nums, pattern):
    m = len(pattern)
    pattern.append(2)
    for i in range(1, len(nums)):
        pattern.append(cmp(nums[i], nums[i-1]))

    n = len(pattern)
    z = [0] * n
    l, r = 0, 0
    ans = 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

    for lcp in z[m+1:]:
        if lcp == m:
            ans += 1

    return ans

def cmp(a, b):
    if a == b:
        return 0
    elif a < b:
        return -1
    else:
        return 1

nums = [1, 2, 3, 4, 5, 6]
pattern = [1, 1]
print(countMatchingSubarrays(nums, pattern))