力扣刷题DAY6（滑动窗口/中等+栈/简单、中等）

一、滑动窗口

找到字符串中所有字母异位词

方法一：哈希表

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;unordered_map<char, int> target;for (int i = 0; i < p.size(); i++) {target[p[i]]++;}int l = 0, r = 0;unordered_map<char, int> window;while (r < s.size()) {window[s[r]]++;if (r - l + 1 == p.size()) {if (target == window)ans.emplace_back(l);window[s[l]]--;if (window[s[l]] == 0)window.erase(s[l]);l++;}r++;}return ans;}
};

思路：

复杂度分析

• 时间复杂度：O(n)：r 线性遍历 s，每次操作 window 仅 O(1)。
• 空间复杂度：O(1)（哈希表最多存 26 个字母）。

 优化版本：

(因为是字母，所以用两个数组替换哈希表)

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;int target[26] = {}; // 初始化for (char c : p) {target[c - 'a']++;}int l = 0, r = 0;int window[26] = {}; // 初始化while (r < s.size()) {window[s[r] - 'a']++;if (r - l + 1 == p.size()) {if (memcmp(target, window, sizeof(target)) == 0) // 修正数组比较方式ans.emplace_back(l);window[s[l] - 'a']--;l++;}r++;}return ans;}
};

 再优化版本：

(用 cnt[c]-- 和 cnt[c]++ 直接调整窗口，避免窗口每次移动都重新统计字符频率。)

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;int cnt[26]{}; // 统计 p 的每种字母的出现次数for (char c : p) {cnt[c - 'a']++;}int left = 0;for (int right = 0; right < s.size(); right++) {int c = s[right] - 'a';cnt[c]--; // 右端点字母进入窗口while (cnt[c] < 0) { // 字母 c 太多了cnt[s[left] - 'a']++; // 左端点字母离开窗口left++; }if (right - left + 1 == p.length()) { // s' 和 p 的每种字母的出现次数都相同ans.push_back(left); // s' 左端点下标加入答案}}return ans;}
};

二、栈

有效的括号

 方法一：vector

class Solution {
public:bool isValid(string s) {vector<char> cnt;for (int i = 0; i < s.size(); i++) {if (s[i] == '(')cnt.emplace_back(s[i]);else if (s[i] == '[')cnt.emplace_back(s[i]);else if (s[i] == '{')cnt.emplace_back(s[i]);else if (s[i] == ')') {if (cnt.size() && cnt.back() == '(') {cnt.pop_back();continue;} elsereturn false;} else if (s[i] == ']') {if (cnt.size() && cnt.back() == '[') {cnt.pop_back();continue;} elsereturn false;} else if (s[i] == '}') {if (cnt.size() && cnt.back() == '{') {cnt.pop_back();continue;} elsereturn false;}}if (!cnt.size())return true;elsereturn false;}
};

 方法二：栈

class Solution {
public:bool isValid(string s) {int n = s.size();if (n % 2 == 1) {return false;}unordered_map<char, char> pairs = {{')', '('},{']', '['},{'}', '{'}};stack<char> stk;for (char ch: s) {if (pairs.count(ch)) {if (stk.empty() || stk.top() != pairs[ch]) {return false;}stk.pop();}else {stk.push(ch);}}return stk.empty();}
};