Kimi k2.6 LeetCode 3036. 匹配模式数组的子数组数目 II Go实现

这道题的核心思路是 KMP 字符串匹配。

思路

1. 预处理：将 `nums` 数组中相邻元素的差值符号提取出来，得到长度为 `n-1` 的 `diff` 数组：
- `nums[i+1] > nums[i]` → `diff[i] = 1`
- `nums[i+1] == nums[i]` → `diff[i] = 0`
- `nums[i+1] < nums[i]` → `diff[i] = -1`

2. KMP 匹配：问题转化为在 `diff` 数组中统计 `pattern` 出现的次数。由于数据范围最大为 10^6，必须使用 KMP 算法在 O(n+m) 时间内完成。

Go 实现

```go
func countMatchingSubarrays(nums []int, pattern []int) int {
n := len(nums)
if n <= 1 {
return 0
}

// 1. 预处理 nums，得到相邻元素的符号数组 diff
diff := make([]int, n-1)
for i := 1; i < n; i++ {
diff[i-1] = getSign(nums[i-1], nums[i])
}

// 2. 使用 KMP 算法统计 pattern 在 diff 中的出现次数
return kmp(diff, pattern)
}

// 计算两个数的符号关系
func getSign(a, b int) int {
if a < b {
return 1
}
if a > b {
return -1
}
return 0
}

// KMP 算法，返回 pattern 在 text 中的出现次数（允许重叠）
func kmp(text, pattern []int) int {
m := len(pattern)
if m == 0 {
return len(text) + 1
}
if len(text) < m {
return 0
}

lps := buildLPS(pattern)
count := 0
i, j := 0, 0 // i 指向 text，j 指向 pattern

for i < len(text) {
if text[i] == pattern[j] {
i++
j++
if j == m {
count++ // 找到一个匹配
j = lps[j-1] // 继续匹配下一个（允许重叠）
}
} else if j > 0 {
j = lps[j-1] // 回退到最长公共前缀
} else {
i++ // pattern[0] 都不匹配，text 指针前进
}
}
return count
}

// 构建 pattern 的最长公共前后缀数组 (LPS)
func buildLPS(pattern []int) []int {
m := len(pattern)
lps := make([]int, m)

for i, j := 1, 0; i < m; i++ {
for j > 0 && pattern[i] != pattern[j] {
j = lps[j-1]
}
if pattern[i] == pattern[j] {
j++
lps[i] = j
}
}
return lps
}
```

复杂度分析

- 时间复杂度：O(n + m)。预处理 O(n)，KMP 匹配 O(n + m)。
- 空间复杂度：O(n + m)。`diff` 数组占用 O(n)，LPS 数组占用 O(m)。