题目描述：
给你一个下标从 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 子数组的 数目 。
数据范围：
$2\le nums.len \le 10^6, 1\le nums[i] \le 10^9, -1 \le pattern[i] \le 1$
题解：
遍历 $nums$ ，创建一个新数组，将 $nums$ 中相邻数字之前的大小关系转化为 $-1, 1, 0$ 存入新数组中。然后使用 $pattern$ 数组作为模式串匹配新数组，求 $pattern$ 在数组中出现的次数。
求匹配次数时，如果出现了匹配，就假设最后一位不匹配，继续 $j = Next[j]$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e6 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int Next[maxn];
void getNext(vector<int> &s)
{
int n = s.size();
Next[0] = -1;
for (int t = -1, i = 0; i < n; Next[++i] = ++t)
{
for (; ~t && s[i] != s[t]; t = Next[t])
;
}
}
int kmp(vector<int> &s, vector<int> &substr)
{
int i = 0, j = 0;
int ans = 0;
int len1 = s.size(), len2 = substr.size();
while (i < len1)
{
if (j == -1 || s[i] == substr[j])
{
++i;
++j;
}
else
{
j = Next[j];
}
if (j == len2)
{
ans++;
--i;
--j;
j = Next[j];
}
}
return ans;
}
int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern)
{
vector<int> num1;
int n = nums.size();
for (int i = 1; i < n; ++i)
{
int tmp = nums[i] - nums[i - 1];
if (tmp == 0)
num1.push_back(0);
else if (tmp > 0)
num1.push_back(1);
else
num1.push_back(-1);
}
getNext(pattern);
return kmp(num1, pattern);
}
};
|