企业官网建设流程全解析

封装系统如何做自己的网站,南京学校网站建设策划,网站前置审批项 教育,织梦网站模板教程一、题目理解#xff1a;什么是 “异位词子串”#xff1f; 简单说#xff1a;字符串s中#xff0c;长度和p相等、且字符出现次数完全一致的子串#xff0c;就是我们要找的 “异位词子串”#xff0c;最终返回这些子串的起始索引。 比如示例 1 里#xff0c;pabc…一、题目理解什么是 “异位词子串”简单说字符串s中长度和p相等、且字符出现次数完全一致的子串就是我们要找的 “异位词子串”最终返回这些子串的起始索引。比如示例 1 里pabc长度 3scbaebacbd中cba索引 0、bac索引 6都是abc的异位词。二、核心思路滑动窗口 字符频率数组异位词的本质是 “字符频率完全匹配”所以我们可以用一个长度为 26 的数组对应 26 个小写字母统计p的字符频率再用滑动窗口在s中动态维护当前窗口的字符频率一旦窗口长度等于p的长度就说明找到了一个异位词子串。三、代码逐行解析C 版直接看代码 注释逻辑超清晰cppclass Solution { public: vectorint findAnagrams(string s, string p) { vectorint v; // 存储结果异位词子串的起始索引 int ch[26] {0}; // 统计p的字符频率初始全0 // 1. 先统计p中每个字符的出现次数 for(int i0; ip.size(); i) ch[p[i]-a]; // 比如p[i]是a则ch[0] int left0; // 滑动窗口的左边界 // 2. 右边界right遍历s的每个字符 for(int right0; rights.size(); right) { int c s[right]-a; // 当前字符对应的数组下标 ch[c]--; // 窗口右移当前字符进入窗口频率-1 // 3. 若当前字符频率0说明窗口里该字符多了左边界右移“挤掉”多余字符 while(ch[c]0) { ch[s[left]-a]; // 左边界字符移出窗口频率1 left; // 左边界右移 } // 4. 当窗口长度等于p的长度时说明找到异位词 if(right-left1 p.size()) v.push_back(left); // 记录当前窗口的起始索引left } return v; } };四、为什么这个思路高效滑动窗口的时间复杂度是O(n)n 是s的长度因为left和right都只遍历一次字符频率数组的空间复杂度是O(1)固定 26 个元素属于 “时间换空间” 的最优解之一。五、实战小技巧遇到 “子串匹配 字符频率” 类题目优先考虑滑动窗口 固定长度数组的组合用数组统计目标串的频率窗口在原串中动态维护频率窗口长度匹配时直接记录结果