滑动窗口 labuladong,lee76 最小覆盖字串、lee567 字符串的排列、 lee438 找到字符串中所有字母异位词、 lee3 无重复字符的最长子串

lee76 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例： 输入: S = “ADOBECODEBANC”, T = “ABC” 输出: “BANC”

说明： 如果 S 中不存这样的子串，则返回空字符串 “”。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

滑动窗口 labuladong想法

注意：解决了，Integer自动拆箱这边 需要强制转化一下int，Integer会缓存频繁使用的数值，数值范围为-128到127，在此范围内直接返回缓存值。==判断时，如果在这个范围 都返回true

数值范围为-128到127，在此范围内直接返回缓存值。

class Solution { public String minWindow(String s, String t) { HashMap<Character, Integer> need = new HashMap<>(); HashMap<Character, Integer> window = new HashMap<>(); // 存需要的字母，可能会有重复 for (int i = 0; i < t.length(); i++) { char curChar = t.charAt(i); need.put(curChar, need.getOrDefault(curChar, 0) + 1); } int left = 0, right = 0; int valid = 0; int start = 0, minLen = Integer.MAX_VALUE; while (right < s.length()) { char c = s.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if ((int)window.get(c) ==(int) need.get(c)) {// 强转 valid++; } } // 判断左侧窗口 while (valid == need.size()) { if (right - left < minLen) { start = left; minLen = right - left; } char d = s.charAt(left); left++; if (need.containsKey(d)) { if ((int)window.get(d) ==(int) need.get(d)) {// 强转 valid--; } window.put(d, window.get(d) - 1); } } } return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); } }

这类题目应该想着四点： 1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？ 2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？ 3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？ 4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

类似：lee567 字符串的排列

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1. 本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。 2. 当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。 至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

修改了lee76的代码

class Solution { public boolean checkInclusion(String s1, String s2) { HashMap<Character, Integer> need = new HashMap<>(); HashMap<Character, Integer> window = new HashMap<>(); // 存需要的字母，可能会有重复 for (int i = 0; i < s1.length(); i++) { char curChar = s1.charAt(i); need.put(curChar, need.getOrDefault(curChar, 0) + 1); } int left = 0, right = 0; int valid = 0; while (right < s2.length()) { char c = s2.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if ((int)window.get(c) ==(int) need.get(c)) { valid++; } } // 判断左侧窗口 while (right-left >= s1.length()) { if(valid == need.size()) return true; char d = s2.charAt(left); left++; if (need.containsKey(d)) { if ((int)window.get(d) ==(int) need.get(d)) { valid--; } window.put(d, window.get(d) - 1); } } } return false; } }

lee438 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明： 字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。 示例 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” 的字母异位词。

solution 直接修改之前的

选left移动时判断：

while (right-left >= p.length()) { if(right-left == p.length() && valid == need.size()){ list.add(left); } class Solution { public List<Integer> findAnagrams(String s, String p) { HashMap<Character, Integer> need = new HashMap<>(); HashMap<Character, Integer> window = new HashMap<>(); List<Integer> list = new ArrayList<>(); // 存需要的字母，可能会有重复 for (int i = 0; i < p.length(); i++) { char curChar = p.charAt(i); need.put(curChar, need.getOrDefault(curChar, 0) + 1); } int left = 0, right = 0; int valid = 0; int start = 0, minLen = Integer.MAX_VALUE; while (right < s.length()) { char c = s.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if ((int)window.get(c) ==(int) need.get(c)) { valid++; } } // 判断左侧窗口 while (right-left >= p.length()) { if(right-left == p.length() && valid == need.size()){ list.add(left); } char d = s.charAt(left); left++; if (need.containsKey(d)) { if ((int)window.get(d) ==(int) need.get(d)) { valid--; } window.put(d, window.get(d) - 1); } } } return list; } }

lee3 无重复字符的最长子串

这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。

唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

class Solution { public int lengthOfLongestSubstring(String s) { // HashMap<Character, Integer> need = new HashMap<>(); HashMap<Character, Integer> window = new HashMap<>(); char[] str = s.toCharArray(); // for (int i = 0; i < s.length(); i++) { // need.put(str[i], need.getOrDefault(str[i], 0) + 1); // } int left = 0, right = 0; // int valid = 0; int maxStr = 0; while (right < s.length()) { char c = str[right]; right++; window.put(c, window.getOrDefault(c, 0) + 1); while (window.get(c) > 1) { char sc = str[left]; left++; window.put(sc, window.get(sc) - 1); } maxStr = Math.max(maxStr, right - left); } return maxStr; } }