Every day a Leetcode
题目来源：3034. 匹配模式数组的子数组数目 I
解法1：暴力遍历
设数组 nums 的长度为 m，数组 pattern 的长度为 n。
遍历数组 nums 的每个长度是 n+1 的子数组并计算子数组的模式，然后与数组 pattern 比较，如果相等则找到一个匹配模式数组的子数组。遍历结束之后即可得到匹配模式数组的子数组数目。
代码：
/** @lc app=leetcode.cn id=3034 lang=cpp** [3034] 匹配模式数组的子数组数目 I*/// @lc code=start
class Solution
{
public:int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern){// 特判if (nums.empty() || pattern.empty())return 0;if (nums.size() <= pattern.size())return 0;int count = 0;int m = nums.size(), n = pattern.size();for (int i = 0; i < m - n; i++){bool flag = true;for (int k = 0; k < n && flag; k++){int diff = nums[i + k + 1] - nums[i + k];int p = getPattern(diff);if (p != pattern[k])flag = false;}if (flag)count++;}return count;}// 辅函数 - 计算 patternint getPattern(int diff){if (diff == 0)return 0;return diff > 0 ? 1 : -1;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O((m-n)*n)，其中 m 为数组 nums 的长度，n 为数组 pattern 的长度。
空间复杂度：O(1)。
解法2：求数组 nums 的匹配模式数组再比较
代码：
/** @lc app=leetcode.cn id=3034 lang=cpp** [3034] 匹配模式数组的子数组数目 I*/// @lc code=start
class Solution
{
public:int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern){// 特判if (nums.empty() || pattern.empty())return 0;if (nums.size() <= pattern.size())return 0;int count = 0;int m = nums.size(), n = pattern.size();vector<int> patterns;for (int i = 0; i < m - 1; i++){int diff = nums[i + 1] - nums[i];int p = getPattern(diff);patterns.push_back(p);}for (int i = 0; i < m - n; i++){vector<int> temp(patterns.begin() + i, patterns.begin() + i + n);if (temp == pattern)count++;}return count;}// 辅函数 - 计算 patternint getPattern(int diff){if (diff == 0)return 0;return diff > 0 ? 1 : -1;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O((m-n)*m)，其中 m 为数组 nums 的长度，n 为数组 pattern 的长度。
空间复杂度：O(m)，其中 m 为数组 nums 的长度。
