滑动窗口
将嵌套的循环转换为单循环问题,降低时间复杂度为O(n)
识别关键字
连续的元素,比如string, subarray, LinkedListmin, max, longest, shortest, key word模板
void slidingWindow(String s, String t){Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for(char c : t.toCharArray()){need.put(c, need.getOrDefault(c, 0)+1);}int left = 0, right = 0;int valid = 0;while (right < s.length()){// c is the character that will be moved into the windowchar c = s.charAt(right);// Move window rightright++;// Update data of the windowif (need.containsKey(c)){window.put(c, window.getOrDefault(c, 0)+1);}while(the left window needs to be moved right){// d is the character that will be moved out of the windowchar d = s.charAt(left);left++;if (need.containsKey(d)){window.put(d, window.get(d)-1);}}}}
两种方式用来存储窗口数据:
//arrayint[] array = new int[26];for (char c: s.toCharArray()) {array[c - 'a']++;}//hashmapMap<Character, Integer> map = new HashMap<>();for (char c: s.toCharArray()) {map.put(c, map.getOrDefault(c, 0)+1);}