力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解

Problem: 438. 找到字符串中所有字母异位词

思路

👩‍🏫 参考题解

滑动窗口 + 数组

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

class Solution {
//	滑动窗口 + 数组public List<Integer> findAnagrams(String s, String p){int n = s.length();int m = p.length();List<Integer> ans = new ArrayList<>();if (n < m)return ans;int[] pp = new int[26];int[] ss = new int[26];for (int i = 0; i < m; i++){pp[p.charAt(i) - 'a']++;ss[s.charAt(i) - 'a']++;}if (Arrays.equals(pp, ss))ans.add(0);for (int i = m; i < n; i++){ss[s.charAt(i - m) - 'a']--;ss[s.charAt(i) - 'a']++;if (Arrays.equals(ss, pp))ans.add(i - m + 1);}return ans;}
}

滑动窗口 + 双指针

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

class Solution {public List<Integer> findAnagrams(String s, String p){int n = s.length();int m = p.length();List<Integer> ans = new ArrayList<>();if (n < m)return ans;int[] pp = new int[26];// 目标串的字符数int[] win = new int[26];// 当前窗口拥有的字符数for (int i = 0; i < m; i++)pp[p.charAt(i) - 'a']++;int l = 0;for (int r = 0; r < n; r++){int rightIdx = s.charAt(r) - 'a';win[rightIdx]++;// 加入r字符导致 当前窗口字符个数超出范围，只能移除左边的字符while (win[rightIdx] > pp[rightIdx]){int leftIdx = s.charAt(l) - 'a';win[leftIdx]--;l++;}
//			注意：走到这，只有 当前窗口内字符数不够 这种情况，上边的while循环保证了当前的窗口的每个字符肯定 <= 目标数if (r - l + 1 == m)// 只要当前窗口大小 == 目标串长度ans.add(l);}return ans;}
}