尧图网页设计 
1. 题目背景与核心需求解析字母异位词Anagram是算法面试中的经典题型指由相同字母重新排列形成的不同单词。力扣LeetCodehot100将其列为高频考点考察的核心能力在于如何高效判断子串是否符合特定条件。这道题的具体要求是给定字符串s和p找出s中所有p的字母异位词的起始索引。例如输入: s cbaebabacd, p abc输出: [0,6] 解释索引0的子串cba是abc的异位词索引6的子串bac是abc的异位词1.1 问题难点拆解时间复杂度控制暴力解法需要O(n*m)时间复杂度n为s长度m为p长度无法通过力扣测试用例哈希计数同步需要实时维护窗口内字符计数与目标p的匹配状态边界条件处理包括空字符串、s长度小于p等特殊情况2. 滑动窗口与哈希计数方案设计2.1 算法选择依据采用滑动窗口哈希计数的组合方案主要基于以下考量滑动窗口优势将时间复杂度从O(n^2)降至O(n)通过窗口滑动避免重复计算天然适配子串类问题哈希计数价值快速比较字符频率使用数组替代HashMap提升性能ASCII字符范围确定时统计维度可扩展如Unicode需改用HashMap2.2 核心数据结构设计// 使用26位数组记录字母频率假设仅含小写字母 int[] pCount new int[26]; int[] windowCount new int[26]; // 初始化p的字符计数 for (char c : p.toCharArray()) { pCount[c - a]; }注意若考虑大小写或Unicode需改用HashMapCharacter, Integer实现3. Java实现详解3.1 完整算法实现public ListInteger findAnagrams(String s, String p) { ListInteger result new ArrayList(); if (s.length() p.length()) return result; int[] pCount new int[26]; int[] windowCount new int[26]; int windowSize p.length(); // 初始化p的字符计数 for (char c : p.toCharArray()) { pCount[c - a]; } // 初始窗口 for (int i 0; i windowSize; i) { windowCount[s.charAt(i) - a]; } if (Arrays.equals(pCount, windowCount)) { result.add(0); } // 滑动窗口 for (int i windowSize; i s.length(); i) { // 移除左边界的字符 windowCount[s.charAt(i - windowSize) - a]--; // 添加右边界的字符 windowCount[s.charAt(i) - a]; if (Arrays.equals(pCount, windowCount)) { result.add(i - windowSize 1); } } return result; }3.2 关键步骤解析窗口初始化先处理第一个窗口0到p.length()-1直接比较初始窗口是否匹配滑动过程每次移动移除最左字符计数添加新进入的右字符计数比较当前窗口与目标计数匹配判断使用Arrays.equals()比较数组记录索引时注意1修正滑动后左边界位置4. 优化与变种方案4.1 单哈希表优化使用单个变量记录有效匹配数避免每次全量比较int[] count new int[26]; int matched 0; for (char c : p.toCharArray()) count[c - a]; for (int l 0, r 0; r s.length(); r) { if (--count[s.charAt(r) - a] 0) matched; if (r - l 1 p.length()) { if (count[s.charAt(l) - a] 0) matched--; } if (matched p.length()) { result.add(l); } }4.2 不同语言实现差异语言哈希实现特殊处理性能关键点Java数组边界检查System.arraycopyPython字典Unicode支持collections.CounterCunordered_map内存预分配reserve()提前分配5. 常见问题与调试技巧5.1 典型错误案例索引越界未检查s.length() p.length()滑动时右边界超出范围计数错误窗口滑动时增减顺序错误字符到数组索引转换错误如未减a性能问题使用ArrayList而非原生数组频繁创建新哈希表5.2 调试建议打印中间状态System.out.println(Window [ left , right ]: Arrays.toString(windowCount));单元测试用例Test public void testEdgeCases() { assertArrayEquals(new int[]{}, findAnagrams(, abc)); assertArrayEquals(new int[]{0}, findAnagrams(a, a)); assertArrayEquals(new int[]{0,1,2}, findAnagrams(abab, ab)); }性能测试方法long start System.nanoTime(); // 执行算法 System.out.println(Time: (System.nanoTime()-start)/1e6 ms);6. 工程实践建议API设计原则输入参数校验null检查、空字符串处理返回不可变列表return Collections.unmodifiableList(result);内存优化技巧重用计数数组而非每次新建预估结果列表大小result new ArrayList(s.length() - p.length() 1)多线程安全考虑若需并发调用应将计数数组改为方法局部变量避免使用静态变量维护状态在实际面试中建议先陈述暴力解法O(n*m)再引出优化方案展示思维过程。对于follow-up问题如超大字符集处理可讨论改用HashMap的trade-off布隆过滤器等概率数据结构应用分布式场景下的分治策略 滑动窗口与哈希计数解决字母异位词问题
1. 题目背景与核心需求解析字母异位词Anagram是算法面试中的经典题型指由相同字母重新排列形成的不同单词。力扣LeetCodehot100将其列为高频考点考察的核心能力在于如何高效判断子串是否符合特定条件。这道题的具体要求是给定字符串s和p找出s中所有p的字母异位词的起始索引。例如输入: s cbaebabacd, p abc输出: [0,6] 解释索引0的子串cba是abc的异位词索引6的子串bac是abc的异位词1.1 问题难点拆解时间复杂度控制暴力解法需要O(n*m)时间复杂度n为s长度m为p长度无法通过力扣测试用例哈希计数同步需要实时维护窗口内字符计数与目标p的匹配状态边界条件处理包括空字符串、s长度小于p等特殊情况2. 滑动窗口与哈希计数方案设计2.1 算法选择依据采用滑动窗口哈希计数的组合方案主要基于以下考量滑动窗口优势将时间复杂度从O(n^2)降至O(n)通过窗口滑动避免重复计算天然适配子串类问题哈希计数价值快速比较字符频率使用数组替代HashMap提升性能ASCII字符范围确定时统计维度可扩展如Unicode需改用HashMap2.2 核心数据结构设计// 使用26位数组记录字母频率假设仅含小写字母 int[] pCount new int[26]; int[] windowCount new int[26]; // 初始化p的字符计数 for (char c : p.toCharArray()) { pCount[c - a]; }注意若考虑大小写或Unicode需改用HashMapCharacter, Integer实现3. Java实现详解3.1 完整算法实现public ListInteger findAnagrams(String s, String p) { ListInteger result new ArrayList(); if (s.length() p.length()) return result; int[] pCount new int[26]; int[] windowCount new int[26]; int windowSize p.length(); // 初始化p的字符计数 for (char c : p.toCharArray()) { pCount[c - a]; } // 初始窗口 for (int i 0; i windowSize; i) { windowCount[s.charAt(i) - a]; } if (Arrays.equals(pCount, windowCount)) { result.add(0); } // 滑动窗口 for (int i windowSize; i s.length(); i) { // 移除左边界的字符 windowCount[s.charAt(i - windowSize) - a]--; // 添加右边界的字符 windowCount[s.charAt(i) - a]; if (Arrays.equals(pCount, windowCount)) { result.add(i - windowSize 1); } } return result; }3.2 关键步骤解析窗口初始化先处理第一个窗口0到p.length()-1直接比较初始窗口是否匹配滑动过程每次移动移除最左字符计数添加新进入的右字符计数比较当前窗口与目标计数匹配判断使用Arrays.equals()比较数组记录索引时注意1修正滑动后左边界位置4. 优化与变种方案4.1 单哈希表优化使用单个变量记录有效匹配数避免每次全量比较int[] count new int[26]; int matched 0; for (char c : p.toCharArray()) count[c - a]; for (int l 0, r 0; r s.length(); r) { if (--count[s.charAt(r) - a] 0) matched; if (r - l 1 p.length()) { if (count[s.charAt(l) - a] 0) matched--; } if (matched p.length()) { result.add(l); } }4.2 不同语言实现差异语言哈希实现特殊处理性能关键点Java数组边界检查System.arraycopyPython字典Unicode支持collections.CounterCunordered_map内存预分配reserve()提前分配5. 常见问题与调试技巧5.1 典型错误案例索引越界未检查s.length() p.length()滑动时右边界超出范围计数错误窗口滑动时增减顺序错误字符到数组索引转换错误如未减a性能问题使用ArrayList而非原生数组频繁创建新哈希表5.2 调试建议打印中间状态System.out.println(Window [ left , right ]: Arrays.toString(windowCount));单元测试用例Test public void testEdgeCases() { assertArrayEquals(new int[]{}, findAnagrams(, abc)); assertArrayEquals(new int[]{0}, findAnagrams(a, a)); assertArrayEquals(new int[]{0,1,2}, findAnagrams(abab, ab)); }性能测试方法long start System.nanoTime(); // 执行算法 System.out.println(Time: (System.nanoTime()-start)/1e6 ms);6. 工程实践建议API设计原则输入参数校验null检查、空字符串处理返回不可变列表return Collections.unmodifiableList(result);内存优化技巧重用计数数组而非每次新建预估结果列表大小result new ArrayList(s.length() - p.length() 1)多线程安全考虑若需并发调用应将计数数组改为方法局部变量避免使用静态变量维护状态在实际面试中建议先陈述暴力解法O(n*m)再引出优化方案展示思维过程。对于follow-up问题如超大字符集处理可讨论改用HashMap的trade-off布隆过滤器等概率数据结构应用分布式场景下的分治策略