滑动窗口法

617076674 · 617076674 · commit 3589547e6271 · 2020-05-04T10:42:30.000+08:00
diff --git a/question0003_longest_substring_without_repeating_characters/Solution2.java b/question0003_longest_substring_without_repeating_characters/Solution2.java
@@ -11,21 +11,18 @@
  */
 public class Solution2 {
     public int lengthOfLongestSubstring(String s) {
-        int n;
-        if (null == s || (n = s.length()) == 0) {
-            return 0;
-        }
-        boolean[] appear = new boolean[256];
-        int left = 0, right = -1, result = 0; //滑动窗口范围是[left, right]
-        while (right + 1 < n) {
-            if (!appear[s.charAt(right + 1)]) {
-                right++;
-                appear[s.charAt(right)] = true;
-            } else {
-                appear[s.charAt(left)] = false; //因为滑动窗口中不可能包含重复字符，故去除left处的字符后，滑动窗口将不包含该字符
+        int[] window = new int[256];
+        int left = 0, right = 0, result = 0; //滑动窗口范围是[left, right)
+        while (right < s.length()) {
+            char cRight = s.charAt(right);
+            right++;
+            window[cRight]++;
+            while (window[cRight] > 1) {
+                char cLeft = s.charAt(left);
                 left++;
+                window[cLeft]--;
             }
-            result = Math.max(result, right - left + 1);
+            result = Math.max(result, right - left);
         }
         return result;
     }
diff --git a/question0076_minimum_window_substring/Solution.java b/question0076_minimum_window_substring/Solution.java
@@ -0,0 +1,39 @@
+package question0076_minimum_window_substring;
+
+/**
+ * 滑动窗口法。
+ *
+ * 时间复杂度是O(n1 + n2)，其中n1为字符串s的长度，n2为字符串t的长度。空间复杂度是O(1)。
+ *
+ * 执行用时：8ms，击败77.99%。消耗内存：40.1MB，击败13.33%。
+ */
+public class Solution {
+    public String minWindow(String s, String t) {
+        int[] window = new int[256], tMap = new int[256];
+        for (int i = 0; i < t.length(); i++) {
+            tMap[t.charAt(i)]++;
+        }
+        String result = s + "a";
+        int left = 0, right = 0, need = t.length();
+        while (right < s.length()) {
+            char cRight = s.charAt(right);
+            window[cRight]++;
+            if (window[cRight] <= tMap[cRight]) {
+                need--;
+            }
+            right++;
+            while (need == 0) {
+                if (right - left < result.length()) {
+                    result = s.substring(left, right);
+                }
+                char cLeft = s.charAt(left);
+                window[cLeft] = window[cLeft] - 1;
+                if (window[cLeft] < tMap[cLeft]) {
+                    need++;
+                }
+                left++;
+            }
+        }
+        return result.length() == s.length() + 1 ? "" : result;
+    }
+}
diff --git a/question0438_find_all_anagrams_in_a_string/Solution.java b/question0438_find_all_anagrams_in_a_string/Solution.java
@@ -0,0 +1,42 @@
+package question0438_find_all_anagrams_in_a_string;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 滑动窗口法。
+ *
+ * 时间复杂度是O(n1 + n2)，其中n1为字符串s的长度，n2为字符串p的长度。
+ *
+ * 执行用时：12ms，击败65.27%。消耗内存：41MB，击败5.88%。
+ */
+public class Solution {
+    public List<Integer> findAnagrams(String s, String p) {
+        int[] window = new int[26], pMap = new int[26];
+        for (int i = 0; i < p.length(); i++) {
+            pMap[p.charAt(i) - 'a']++;
+        }
+        int left = 0, right = 0, need = p.length();
+        List<Integer> result = new ArrayList<>();
+        while (right < s.length()) {
+            char cRight = s.charAt(right);
+            right++;
+            window[cRight - 'a']++;
+            if (window[cRight - 'a'] <= pMap[cRight - 'a']) {
+                need--;
+            }
+            while (right - left > p.length()) {
+                char cLeft = s.charAt(left);
+                left++;
+                window[cLeft - 'a']--;
+                if (window[cLeft - 'a'] < pMap[cLeft - 'a']) {
+                    need++;
+                }
+            }
+            if (right - left == p.length() && need == 0) {
+                result.add(left);
+            }
+        }
+        return result;
+    }
+}
diff --git a/question0567/Solution.java b/question0567/Solution.java
diff --git a/question0567_permutation_in_string/Solution.java b/question0567_permutation_in_string/Solution.java
@@ -0,0 +1,38 @@
+package question0567_permutation_in_string;
+
+/**
+ * 滑动窗口法。
+ *
+ * 时间复杂度是O(n1 + n2)，其中n1为字符串s1的长度，n2为字符串s2的长度。空间复杂度是O(1)。
+ *
+ * 执行用时：10ms，击败57.67%。消耗内存：39.6MB，击败18.75%。
+ */
+public class Solution {
+    public boolean checkInclusion(String s1, String s2) {
+        int[] window = new int[26], s1Map = new int[26];
+        for (int i = 0; i < s1.length(); i++) {
+            s1Map[s1.charAt(i) - 'a']++;
+        }
+        int left = 0, right = 0, need = s1.length();
+        while (right < s2.length()) {
+            char cRight = s2.charAt(right);
+            window[cRight - 'a']++;
+            if (window[cRight - 'a'] <= s1Map[cRight - 'a']) {
+                need--;
+            }
+            right++;
+            while (right - left > s1.length()) {
+                char cLeft = s2.charAt(left);
+                left++;
+                window[cLeft - 'a']--;
+                if (window[cLeft - 'a'] < s1Map[cLeft - 'a']) {
+                    need++;
+                }
+            }
+            if (right - left == s1.length() && need == 0) {
+                return true;
+            }
+        }
+        return false;
+    }
+}
diff --git a/question076/Solution.java b/question076/Solution.java
