企业网站托管备案,班级管理网站开发,虹口集团网站建设,html网页制作模板代码用i和j表示滑动窗口的左边界和右边界#xff0c;思路如下#xff1a;
j右移#xff0c;直到i-j内包含住了t的所有元素i右移#xff0c;去除掉左边多余元素保留最小长度#xff0c;同时i右移#xff0c;此时确定i-j的子串一定不能完全覆盖t#xff0c;于是重复1#xf…用i和j表示滑动窗口的左边界和右边界思路如下
j右移直到i-j内包含住了t的所有元素i右移去除掉左边多余元素保留最小长度同时i右移此时确定i-j的子串一定不能完全覆盖t于是重复123步骤。
使用need的HashMap来记录覆盖t中每个元素的所需个数。 为减少复杂度使用needCount来判断是否已经完全覆盖t。 注意need.get(c)有可能小于0这表示s中c的个数多于t中c的个数。
class Solution {public String minWindow(String s, String t) {String ans ;if (t.length() s.length()) return ans;HashMapCharacter, Integer need new HashMap();for (int i 0; i t.length(); i) {char c t.charAt(i);need.put(c, need.getOrDefault(c, 0) 1);}int left 0;int minLeft 0, minLen Integer.MAX_VALUE;int needCount t.length();for (int right 0; right s.length(); right) {char c s.charAt(right);if (need.containsKey(c)) {need.put(c, need.get(c) - 1);// needCount--;if (need.get(c) 0) needCount--;}while (needCount 0) {if (right - left 1 minLen) {minLeft left;minLen right - left 1;}char leftChar s.charAt(left);if (need.containsKey(leftChar)) {need.put(leftChar, need.get(leftChar) 1);// needCount;if (need.get(leftChar) 0) needCount;}left;}}return minLen Integer.MAX_VALUE ? ans : s.substring(minLeft, minLeft minLen);}
}
