网站空间 哪个速度快,何鹏seo,dedecms物流企业网站模板(适合快递,跟京东类似的网站滑动窗口 找到字符串中所有字母异位词滑动窗口数组优化 上期经典 找到字符串中所有字母异位词 难度 - 中等 Leetcode 438 - 找到字符串中所有字母异位词 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出… 滑动窗口 找到字符串中所有字母异位词滑动窗口数组优化 上期经典 找到字符串中所有字母异位词 难度 - 中等 Leetcode 438 - 找到字符串中所有字母异位词 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串包括相同的字符串。 示例 1: 输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 示例 2: 输入: s “abab”, p “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。 提示: 1 s.length, p.length 3 * 1e4 s 和 p 仅包含小写字母 滑动窗口 这个所谓的字母异位词不就是排列吗相当于输入一个串 S一个串 T找到 S 中所有 T 的排列返回它们的起始索引。 因为字符串 p 的异位词的长度一定与字符串 p 的长度相同所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时则说明当前窗口为字符串 p 的异位词。 构造滑动窗口时我们用双指针右指针代表扩大窗口左指针代表缩小窗口在扩大和缩小窗口时我们把满足条件的字符加入到对比的hash 表中 代码演示 /*** 异位* param s* param p* return*/public ListInteger findAnagrams(String s, String p) {HashMapCharacter, Integer need new HashMap();HashMapCharacter, Integer wind new HashMap();//将目标值加进来for (char c : p.toCharArray()){need.put(c,need.getOrDefault(c,0) 1);}int left 0;int right 0;int valid 0;ArrayListInteger ans new ArrayList();while (right s.length()){char c s.charAt(right);right;if (need.containsKey(c)){wind.put(c,wind.getOrDefault(c,0) 1);if (need.get(c).equals(wind.get(c))){valid;}}//判断什么时候缩小窗口while (right - left p.length()){//满足条件时 将起始位置加进去if (valid need.size()){ans.add(left);}char d s.charAt(left);left;if (need.containsKey(d)){if (wind.get(d).equals(need.get(d))){valid--;}wind.put(d,wind.get(d) - 1);}}}return ans;}数组优化 因为 题目中说是小写字母组成的范围就是固定的可以利用数组来优化掉hash 表 带来两个好处 1.时间更快数组的效率高于hash. 2.空间更省数组占用空间小于hash. 代码演示 public ListInteger findAnagrams(String s, String p) {ArrayListInteger ans new ArrayList();int n s.length();int m p.length();if (n m){return ans;}int[] need new int[26];int[] wind new int[26];//将目标值加进来for (char c : p.toCharArray()){need[c - a];}int left 0;int right 0;while (right n){char c s.charAt(right);right;if (need[c - a] ! 0){wind[c - a];}//判断什么时候缩小窗口while (right - left m){//满足条件时 将起始位置加进去if (Arrays.equals(need,wind)){ans.add(left);}char d s.charAt(left);left;if (need[d - a] ! 0){wind[d - a]--;}}}return ans;}
上期经典
leetcode 567. 字符串的排列
