免费申请网站官网,企业推广托管,专业网站制作仪表多少钱,wordpress不同分类模板Problem: 438. 找到字符串中所有字母异位词 文章目录 思路滑动窗口 数组滑动窗口 双指针 思路
#x1f469;#x1f3eb; 参考题解
滑动窗口 数组 ⏰ 时间复杂度: O ( n ) O(n) O(n) #x1f30e; 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
// 滑动窗口 … Problem: 438. 找到字符串中所有字母异位词 文章目录 思路滑动窗口 数组滑动窗口 双指针 思路
参考题解
滑动窗口 数组 ⏰ 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
// 滑动窗口 数组public ListInteger findAnagrams(String s, String p){int n s.length();int m p.length();ListInteger 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(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {public ListInteger findAnagrams(String s, String p){int n s.length();int m p.length();ListInteger 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;}
}
