力扣热门100题之找到字符串中所有字母异位词

核心思路字母异位词 字符种类 每个字符出现次数 完全一样所以解法核心用两个数组分别统计 p 的字符次数、滑动窗口的字符次数相等就是答案核心逻辑用大白话讲1. 两个数组干嘛的need[]p 的字符次数表window[]当前窗口的字符次数表只要两个数组完全一样就是字母异位词2. 为什么用c - a因为字母a~z可以转成数字a - a 0b - a 1...z - a 25这样就能用数组下标代表字母超级快3. 滑动窗口怎么滑动窗口固定长度 p 的长度 n右指针i一直向右走新字符进窗口→window窗口太长→ 最左边字符移出 →window--每次判断窗口是否匹配 need匹配就记录起始下标4. 为什么起始下标是i - n 1举个例子p 长度 n3i 走到下标 2 → 窗口是 [0,1,2] → 起始 0公式2 - 3 1 0i 走到下标 5 → 窗口是 [3,4,5] → 起始 3公式5 - 3 1 3完整代码实现;class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger res new ArrayList(); int[] need new int[26]; int[] window new int[26]; int m s.length(), n p.length(); if (m n) return res; for (char c : p.toCharArray()) { need[c - a]; } for (int i 0; i m; i) { // 加入右指针字符 window[s.charAt(i) - a]; // 窗口超过长度 n左边移出 if (i n) { window[s.charAt(i - n) - a]--; } // 判断窗口是否 need if (Arrays.equals(window, need)) { res.add(i - n 1); } } return res; } }