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完整代码如下：
代码语言：javascript复制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完整代码如下：
代码语言：javascript复制# -*-coding:utf-8-*-
defcountMatchingSubarrays(nums, pattern):
m =len(pattern)
pattern.append(2)
for i inrange(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 inrange(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
defcmp(a, b):
if a == b:
return0
elif a < b:
return-1
else:
return1
nums =[1,2,3,4,5,6]
pattern =[1,1]
print(countMatchingSubarrays(nums, pattern))
