刷题笔记 - 滑动窗口

滑动窗口

所有题目来自leetcode的回答：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai

会员题没有列出来。

最长无重复子串

题目：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length();if (n == 0) return 0;Map<Character, Integer> map = new HashMap<>();int res = 0, left = 0;for (int i = 0; i < n; i ++) {if (map.containsKey(s.charAt(i))) {left = Math.max(left, map.get(s.charAt(i)) + 1);}map.put(s.charAt(i), i);res = Math.max(res, i - left  + 1);}return res;}
}

最小覆盖子串

题目：https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {Map<Character, Integer> cnts = new HashMap<>();Map<Character, Integer> cntt = new HashMap<>();public String minWindow(String s, String t) {int ls = s.length(), lt = t.length();int milen = Integer.MAX_VALUE, st = 0,  ed = 0, mist = 0, mied = 0;boolean isNull = false;for (int i = 0 ; i < lt; i ++) {cntt.put(t.charAt(i), cntt.getOrDefault(t.charAt(i), 0) + 1);}while (ed < ls) {if (cntt.containsKey(s.charAt(ed))) {cnts.put(s.charAt(ed), cnts.getOrDefault(s.charAt(ed), 0) + 1);while (check()) {  // 这里是while，一步更新到第二个在cntt里的字符，过滤掉无用字符isNull = true;if (milen > ed - st + 1) {milen = ed - st + 1;mist = st;mied = ed;}if (cntt.containsKey(s.charAt(st))) {cnts.put(s.charAt(st), cnts.getOrDefault(s.charAt(st), 0) - 1);}st ++;}}ed ++;}if (!isNull) return "";return s.substring(mist, mied + 1);}private boolean check() {Iterator iter = cntt.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry = (Map.Entry) iter.next();Character key = (Character) entry.getKey();Integer val = (Integer) entry.getValue();if (cnts.getOrDefault(key, 0) < val) return false;}return true;}
}

串联所有单词的子串

题目：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

题解：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solutions/3825/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai

// 对words中的所有单词，维护一个单词计数map
// 串联子串中保证了每个子单词的原字符顺序不变
class Solution {public List<Integer> findSubstring(String s, String[] words) {int ls = s.length(), n = words.length;int lw = n * words[0].length(), oneLen = words[0].length();List<Integer> res = new ArrayList<>();if (lw > ls) return res;Map<String, Integer> wordsMap = new HashMap<>();for (int i = 0; i < n; i ++) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);}for (int i = 0; i < ls - lw + 1; i ++) {  //  i < ls - lw + 1，保证能枚举到最后一个窗口的第一个下标位置Map<String, Integer> tmpMap = new HashMap<>();for (int j = i; j < i + lw; j += oneLen) {String subStr = s.substring(j, j + oneLen);tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);}if (wordsMap.equals(tmpMap)) res.add(i);}return res; }
}

优化：（常规的滑动窗口思路，和最小覆盖子串的代码逻辑相似）

class Solution {public List<Integer> findSubstring(String s, String[] words) {int ls = s.length(), n = words.length;int lw = n * words[0].length(), oneLen = words[0].length();List<Integer> res = new ArrayList<>();if (lw > ls) return res;Map<String, Integer> wordsMap = new HashMap<>();for (int i = 0; i < n; i ++) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);}for (int i = 0; i < oneLen; i ++) {  // 保证枚举到所有单词[0...oneLen], [1...oneLen + 1], ...int st = i, ed = i, cnt = 0;Map<String, Integer> tmpMap = new HashMap<>();while (ed < ls - oneLen + 1) {  // 同解法一的判断String subStr = s.substring(ed, ed + oneLen);tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);ed += oneLen;cnt ++;  // 当前窗口里有几个单词while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {// 窗口里的单词并不在wordsMap里，移动窗口// 或者，窗口里当前单词重复出现了，移动窗口String stStr = s.substring(st, st + oneLen);  // 窗口里最左边的单词tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);st += oneLen;cnt --;}if (cnt == n) res.add(st);}}return res;}
}

再优化（直接跳过不在words里的单词和窗口）：

class Solution {public List<Integer> findSubstring(String s, String[] words) {int ls = s.length(), n = words.length;int lw = n * words[0].length(), oneLen = words[0].length();List<Integer> res = new ArrayList<>();if (lw > ls) return res;Map<String, Integer> wordsMap = new HashMap<>();for (int i = 0; i < n; i ++) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);}for (int i = 0; i < oneLen; i ++) {  // 保证枚举到所有单词[0...oneLen], [1...oneLen + 1], ...int st = i, ed = i, cnt = 0;Map<String, Integer> tmpMap = new HashMap<>();while (ed < ls - oneLen + 1) {  // 同解法一的判断String subStr = s.substring(ed, ed + oneLen);ed += oneLen;if (!wordsMap.containsKey(subStr)) {/**当前窗口的当前单词不是words里的单词，肯定不符合题意，更新窗口。题中要求所有串联单词必须挨在一起，这个判断过滤掉不挨在一起的窗口*/cnt = 0;st = ed;tmpMap.clear();continue;}tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);cnt ++;  // 当前窗口里有几个单词while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {// 窗口里的单词并不在wordsMap里，移动窗口// 或者，窗口里当前单词重复出现了，移动窗口String stStr = s.substring(st, st + oneLen);  // 窗口里最左边的单词tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);st += oneLen;cnt --;}if (cnt == n) res.add(st);}}return res;}
}

长度最小的子数组

题目：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int milen = Integer.MAX_VALUE, st = 0, ed = 0, sum = 0;boolean isNull = false;while (ed < n) {sum += nums[ed];while (sum >= target) {isNull = true;if (milen > ed - st + 1) {milen = ed - st + 1;}sum -= nums[st];st ++;}ed ++;}if (!isNull) return 0;return milen;}
}

滑动窗口最大值

题目：https://leetcode.cn/problems/sliding-window-maximum/description/

题解：https://leetcode.cn/problems/sliding-window-maximum/solutions/2361228/239-hua-dong-chuang-kou-zui-da-zhi-dan-d-u6h0

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 借鉴最小栈的思路，再O(1)时间内找出窗口内的最大值// 双向队列维持一个窗口内的非严格递减排序// 队头是窗口内的最大值int n = nums.length;if (k == 1) return nums;int[] res = new int[n - k + 1];Deque<Integer> dq = new LinkedList<>();int idx = 0;for (int i = 0; i < k; i ++) {while (!dq.isEmpty() && dq.peekLast() < nums[i]) {dq.removeLast();}dq.addLast(nums[i]);}res[idx ++] = dq.peekFirst();for (int i = k; i < n; i ++) {if (dq.peekFirst() == nums[i - k]) dq.removeFirst();while (!dq.isEmpty() && dq.peekLast() < nums[i]) {dq.removeLast();}dq.addLast(nums[i]);res[idx ++] = dq.peekFirst();}return res;}
}

字符串的排列

题目：https://leetcode.cn/problems/permutation-in-string/description/

题解-方法二：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solutions/355881/zui-xiao-qu-jian-by-leetcode-solution

class Solution {public boolean checkInclusion(String s1, String s2) {int ls1 = s1.length(), ls2 = s2.length();if (ls1 > ls2) return false;int[] cnt1 = new int[26], cnt2 = new int[26];for (int i = 0; i < ls1; i ++) {cnt1[s1.charAt(i) - 'a'] ++;cnt2[s2.charAt(i) - 'a'] ++;}if (Arrays.equals(cnt1, cnt2)) return true;for (int i = ls1; i < ls2; i ++) {cnt2[s2.charAt(i - ls1) - 'a'] --;cnt2[s2.charAt(i) - 'a'] ++;if (Arrays.equals(cnt1, cnt2)) return true;}return false;}
}

最小区间

题目：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/description/

class Solution {public int[] smallestRange(List<List<Integer>> nums) {int n = nums.size();Map<Integer, List<Integer>> index = new HashMap<>();int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;for (int i = 0; i < n; i ++) {for (int item : nums.get(i)) {List<Integer> tmp = index.getOrDefault(item, new ArrayList<Integer>());tmp.add(i);index.put(item, tmp);if (mi > item) mi = item;if (mx < item) mx = item;}}int st = mi, ed = mi - 1, ansSt = 0, ansEd = Integer.MAX_VALUE, cnt = 0;// System.out.println(mi + ", " + mx);int[] interval = new int[n];   // 记录滑动窗口覆盖了多少区间,下标标识某个区间while (ed < mx) {ed ++;if (index.containsKey(ed)) {for (int idx : index.get(ed)) {  // 枚举被覆盖的区间interval[idx] ++;if (interval[idx] == 1) {  // idx标识的区间第一次被覆盖时，标记该区间被覆盖cnt ++;}while (cnt == n) {  // 当所有区间被覆盖，更新最小区间和窗口if (ed - st < ansEd - ansSt) {// System.out.println("*--*-*-");ansSt = st;ansEd = ed;}if (index.containsKey(st)) {  // 更新最小区间的左端点，看是否能覆盖全部区间for (int leftIdx : index.get(st)) {interval[leftIdx] --;if (interval[leftIdx] == 0) {cnt --;}}}st ++;}}}}return new int[] {ansSt, ansEd};}
}