滑動(dòng)窗口

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

會(huì)員題沒有列出來。

最長無重復(fù)子串

題目：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，一步更新到第二個(gè)在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;}
}

串聯(lián)所有單詞的子串

題目：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

// 對(duì)words中的所有單詞，維護(hù)一個(gè)單詞計(jì)數(shù)map
// 串聯(lián)子串中保證了每個(gè)子單詞的原字符順序不變
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，保證能枚舉到最后一個(gè)窗口的第一個(gè)下標(biāo)位置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; }
}

優(yōu)化：（常規(guī)的滑動(dòng)窗口思路，和最小覆蓋子串的代碼邏輯相似）

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 ++;  // 當(dāng)前窗口里有幾個(gè)單詞while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {// 窗口里的單詞并不在wordsMap里，移動(dòng)窗口// 或者，窗口里當(dāng)前單詞重復(fù)出現(xiàn)了，移動(dòng)窗口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;}
}

再優(yōu)化（直接跳過不在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)) {/**當(dāng)前窗口的當(dāng)前單詞不是words里的單詞，肯定不符合題意，更新窗口。題中要求所有串聯(lián)單詞必須挨在一起，這個(gè)判斷過濾掉不挨在一起的窗口*/cnt = 0;st = ed;tmpMap.clear();continue;}tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);cnt ++;  // 當(dāng)前窗口里有幾個(gè)單詞while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {// 窗口里的單詞并不在wordsMap里，移動(dòng)窗口// 或者，窗口里當(dāng)前單詞重復(fù)出現(xiàn)了，移動(dòng)窗口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;}
}

長度最小的子數(shù)組

題目：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;}
}

滑動(dòng)窗口最大值

題目：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)時(shí)間內(nèi)找出窗口內(nèi)的最大值// 雙向隊(duì)列維持一個(gè)窗口內(nèi)的非嚴(yán)格遞減排序// 隊(duì)頭是窗口內(nèi)的最大值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;}
}

最小區(qū)間

題目：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];   // 記錄滑動(dòng)窗口覆蓋了多少區(qū)間,下標(biāo)標(biāo)識(shí)某個(gè)區(qū)間while (ed < mx) {ed ++;if (index.containsKey(ed)) {for (int idx : index.get(ed)) {  // 枚舉被覆蓋的區(qū)間interval[idx] ++;if (interval[idx] == 1) {  // idx標(biāo)識(shí)的區(qū)間第一次被覆蓋時(shí)，標(biāo)記該區(qū)間被覆蓋cnt ++;}while (cnt == n) {  // 當(dāng)所有區(qū)間被覆蓋，更新最小區(qū)間和窗口if (ed - st < ansEd - ansSt) {// System.out.println("*--*-*-");ansSt = st;ansEd = ed;}if (index.containsKey(st)) {  // 更新最小區(qū)間的左端點(diǎn)，看是否能覆蓋全部區(qū)間for (int leftIdx : index.get(st)) {interval[leftIdx] --;if (interval[leftIdx] == 0) {cnt --;}}}st ++;}}}}return new int[] {ansSt, ansEd};}
}