Every day a Leetcode
題目來源：3036. 匹配模式數組的子數組數目 II
解法1：KMP
設數組 nums 的長度為 m，數組 pattern 的長度為 n。
遍歷數組 nums 的每個長度是 n+1 的子數組并計算子數組的模式，然后與數組 pattern 比較，如果相等則找到一個匹配模式數組的子數組。遍歷結束之后即可得到匹配模式數組的子數組數目。
我們發現這其實就是 KMP。
將匹配模式轉換成字符串：1 對應 ‘a’，0 對應 ‘b’，-1 對應 ‘c’。
代碼：
/** @lc app=leetcode.cn id=3036 lang=cpp** [3036] 匹配模式數組的子數組數目 II*/// @lc code=start// KMPclass Solution
{
private:// KMP 算法vector<int> getNxt(string &pattern){vector<int> nxt;// next[0] 必然是 0nxt.push_back(0);// 從 next[1] 開始求int x = 1, now = 0;while (x < pattern.length()){if (pattern[now] == pattern[x]){// 如果 pattern[now] == pattern[x]，向右拓展一位now++;x++;nxt.push_back(now);}else if (now != 0){// 縮小 now，改成 nxt[now - 1]now = nxt[now - 1];}else{// now 已經為 0，無法再縮小，故 next[x] = 0nxt.push_back(0);x++;}}return nxt;}vector<int> kmp(string &s, string &pattern){int m = pattern.length();vector<int> nxt = getNxt(pattern);vector<int> res;int tar = 0; // 主串中將要匹配的位置int pos = 0; // 模式串中將要匹配的位置while (tar < s.length()){if (s[tar] == pattern[pos]){// 若兩個字符相等，則 tar、pos 各進一步tar++;pos++;}else if (pos != 0){// 失配，如果 pos != 0，則依據 nxt 移動標尺pos = nxt[pos - 1];}else{// pos[0] 失配，標尺右移一位tar++;}if (pos == pattern.length()){res.push_back(tar - pos);pos = nxt[pos - 1];}}return res;}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();// 1 對應 'a'，0 對應 'b'，-1 對應 'c'string s;for (int i = 0; i < m - 1; i++){int diff = nums[i + 1] - nums[i];int p = getPattern(diff);if (p == 1)s += "a";else if (p == 0)s += "b";elses += "c";}string p;for (int &pa : pattern){if (pa == 1)p += "a";else if (pa == 0)p += "b";elsep += "c";}return kmp(s, p).size();}// 輔函數 - 計算 patternint getPattern(int diff){if (diff == 0)return 0;return diff > 0 ? 1 : -1;}
};
// @lc code=end
結果：
復雜度分析：
時間復雜度：O(m)，其中 m 是數組 nums 的長度。
空間復雜度：O(n)，其中 n 是數組 pattern 的長度。
解法2：Z 函數（擴展 KMP）
代碼：
// Z 函數（擴展 KMP）class Solution
{
public:int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern){int m = pattern.size();// 為了防止匹配越界，中間插入一個不在數組中的數字pattern.push_back(2);for (int i = 1; i < nums.size(); i++){int x = nums[i - 1], y = nums[i];// if (x < y)// pattern.push_back(1);// else if (x == y)// pattern.push_back(0);// else// pattern.push_back(-1);pattern.push_back((y > x) - (y < x));}int n = pattern.size();vector<int> z(n);int l = 0, r = 0; // Z box 的左右邊界for (int i = 1; i < n; i++){if (i <= r) // i 在 Z box 內{z[i] = min(z[i - l], r - i + 1);}// 繼續向后暴力匹配while (i + z[i] < n && pattern[z[i]] == pattern[i + z[i]]){l = i;r = i + z[i];z[i]++;}}int ans = 0;for (int i = m + 1; i < n; i++){if (z[i] >= m)ans++;}return ans;}
};
結果：
復雜度分析：
時間復雜度：O(n)，其中 n 是數組 nums 的長度。
空間復雜度：O(n)，其中 n 是數組 nums 的長度。
)
