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-*-

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))

在这里插入图片描述