机试备考笔记 4/31
2025年8月4日
小结：省流版，ac 了两道双指针（哎呀真是，码力退化太明显了，这都要写两个小时+，debug太久，码力太弱）有道写复杂了，虽然超过100%的用户，还是感觉有点亏，哎呀真是，逻辑太弱写太差。有一题TLE等明天debug。今天练习3h+，还可以，产出有点少
目录
- LeetCode
- 3. 无重复字符的最长子串
- 438. 找到字符串中所有字母异位词
- 560. 和为K的子数组
LeetCode
3. 无重复字符的最长子串
3. 无重复字符的最长子串
题目
就是一个字符串，找最长没有重复字符的子串
Acwing 类似题目有，很 ez，但是脑子抽筋改了将近一个小时（理论上二十分钟就该一把 ac 好吗，生气
双指针经典题
- 对
unordered_mapunordered_set用法不熟悉了 - 为了精简代码，在 if 判断外有通用的操作，但是自己忘记了，以为没加实则加了
- 代码不稳健，没考虑到空串的情况
class Solution {
public:int lengthOfLongestSubstring(string s) {int l = s.length();if (l == 0) return 0;unordered_map<char, int> mp;mp[s[0]] = 1;int bg = 0, ed = 1, ans = 1;while (ed < l) {if (mp[s[ed]] != 0) {// 在 ed 没加进来的时候是满足的ans = max(ans, ed - bg);while(bg < ed) {if (s[bg] == s[ed]) {mp[s[bg++]]--;ans = max(ans, ed - bg + 1);break;}mp[s[bg++]]--;}}mp[s[ed++]]++;}ans = max(ans, ed - bg);return ans;}
};
我的写法竟然比官方的快，官方用的是 unordered_set for 循环左指针，右指针在满足的情况下移动，用 insert erase 方法（可能是这个导致的慢）理论上两种写法差不多
| 特性/操作 | unordered_map<K, V> | unordered_set<T> |
|---|---|---|
| 头文件 | #include <unordered_map> | #include <unordered_set> |
| 元素类型 | key-value 键值对 | 单一 key 元素 |
| 插入元素 | mp[key] = value; | st.insert(val); |
| 查找元素 | mp.count(key) | st.count(val) |
| 访问元素 | mp[key] | 无法直接访问，需要迭代器或 count |
| 删除元素 | mp.erase(key) | st.erase(val) |
| 遍历方法 | for (auto item : mp) item.firsrt item.second | for (auto item : st) |
| 初始化方式 | unordered_map<char, int> mp; | unordered_set<int> st; |
| 判断是否存在 | if (mp.count(key)) | if (st.count(val)) |
| 元素个数 | mp.size() | st.size() |
| 清空 | mp.clear(); | st.clear(); |
438. 找到字符串中所有字母异位词
438.找到字符串中所有字母异位词
题目
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
分类讨论+双指针，定一个开头，对这段字符串进行分析：
①遇到子串未出现的字符，ok，重开，开头变成未出现字符的下一个；
②个数超了，要记忆化，把从头到第一个同字符的删掉，后续还要用这剩余的字符串；
③满足条件
1和5是我的同一个思路，唯一优化是数据结构，map set 毕竟是哈希，太慢，既然26个字母，那以后遇到都用数组，绝对的 O(1)
2和6给的是官方的题解，啧，优化后还比我慢
碎碎念：虽然我快，但是写起来的确麻烦，1h里有一半时间都在debug，一则用 ed++ 之流打印中间变量不方便检查了，二则要分清楚加没加，头疼 つ﹏⊂
class Solution {
public:vector<int> findAnagrams(string s, string p) {int l1 = s.length(), l2 = p.length();if (l1 < l2) return {};// 用数组代替 unordered_map 和 unordered_setvector<int> mpp(26, 0); // p中字符计数vector<int> mps(26, 0); // s滑动窗口字符计数for (int i = 0; i < l2; i++) {mpp[p[i] - 'a']++;}vector<int> ans;int bg = 0, ed = 0;while (bg + l2 - 1 < l1) {int flag = 0;while (ed < bg + l2) {int idx = s[ed] - 'a';if (mpp[idx] == 0) {// 不在p中，窗口完全失效// 完犊子了，这个st废了fill(mps.begin(), mps.end(), 0);flag = 1;break;} else {if (mps[idx] < mpp[idx]) {mps[idx]++;ed++;} else {// 个数太多// 完犊子了，这个st又废了flag = 2;break;}}}if (flag == 0) {ans.push_back(bg);mps[s[bg++] - 'a']--;} else if (flag == 1) {bg = ed + 1;ed = bg;} else if (flag == 2) {// 没有完全作废，在[st, ed]双闭区间// 纳入s[ed]会个数超// 因此，第一个同s[ed]后的还可以参考while (s[bg] != s[ed]) {mps[s[bg++] - 'a']--;}ed++, bg++;}}return ans;}
};
560. 和为K的子数组
560. 和为K的子数组
题目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
连续非空，所以想的前缀和，结果TLE了。害，今天也没空继续写了，明天debug了写明天那里