窗口型指针 Sliding window
- 常常用于连续数组/连续String的问题 在given数组中找子数组满足和大于sum
- naive
- for i=0 -> n
- for j=i+1 -> n
- for k=i->j, 求sum
- 优化
- sum = sum + a[j]
- 当sum>s后，j不需要再往后
- 不需要回退 发现很多窗口的计算已经被前一个cover了，所以第二个loop可以改为用
while(j < n)，在这个情形下，j只会一直往前走直到末尾，不会从头在计算，所以最多遍历O(2n)次，时间复杂度为O(n)
for (int i = 0; i < n; i++) {
while (j < n) {
if (满足条件) {
j++;
更新j状态;
} else
break;
}
更新结果集（len, etc）
}
Minimum Size Subarray Sum
- 滑动窗口在subarray中的应用，注意判定条件，这道题里变化的是左窗口
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int ans = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
while (left <= i && sum >= s) {
ans = Math.min(ans, i - left + 1);
sum -= nums[left++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
Substring问题
根据一个String找另一个String的substring
substring满足某些条件。e.g anagram 步骤： 1.Map记录下需要满足的条件，当只有英文字母的时候可以用int[26] 2.两个指针left,right, 一个计数器count为map的大小 3.这时候以right为while循环条件，开始遍历。这时候Map的效用开始变化了，
- 检查rightChar，如果存在于map中，更新map对应的值（map值每次减一，有可能为负数，若是负数的话，则说明有多余的letter）。并且如果更新后的值为0，则说明这个key已经全部满足，count--。接着往下检查
- 而当count==0的时候，说明了满足了条件（特别注意：在这个时候map中所有的value应该都为0了.这里用while是为了让left指针能不断向右移动），这时候可以加入结果集。同时窗口left向后移动一位，于是要对leftChar进行处理，如果leftChar在map中（不一定，因为count为0时候满足条件，但可能仍然有多余的元素），那么更新map，把对应的value+1，此时若value>0了，说明不满足了，count++跳出循环
Find All Anagrams in a String
public List<Integer> findAnagrams(String s, String p) {
List<Integer> results = new ArrayList<>();
if (s == null || s == "" || p == null || p == "") return results;
int len = p.length();
int[] map = new int[26]; //store the freq of each letter
for (int i = 0; i < len; i++){
map[p.charAt(i) - 'a']++;
}
int[] submap = new int[26];
int j = 0;
// the the first substring start from j with the length of p
while (j < len && j < s.length()) {
submap[s.charAt(j++) - 'a']++;
}
j = 0;
if (Arrays.equals(map, submap)) {
results.add(j);
}
while (j < s.length() - len) {
//go to the next substring by removing the top c and add the next char
submap[s.charAt(j) - 'a']--;
submap[s.charAt(j+len) - 'a']++;
j++;
//compare the substring with p
if (Arrays.equals(map, submap)) {
results.add(j);
}
}
return results;
}
若仅仅是针对于一个String本身的，用
Longest Substring without repeating Characters
- 最直接的想法就是，不断的判断下一个字符是否包括在前面的substring中，
- 如果没有包括，则加入进去，
- 如果已经重复了，那么则说明重复的一定是在前面的区间，这里只需要每一次把左边界向右移动一位即可，这样哪怕不是正好重复的那个字母，也可以不断去逼近
- 从第0个点开始去取substring，每一次都记录最大的长度 O(n)
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int size = s.length();
int len = 1, j = 1;
for (int i = 0; i < size; i++) {
while (j < size) {
String sub = s.substring(i, j); //尽量不要用substring，不容易确定是否包括在内
if (sub.indexOf(s.charAt(j)) == -1) {
j++;
} else {
break;
}
}
len = Math.max(len, j - i);
}
return len;
}
//Optimized 在遇到这种no repeat/duplicate 的情况，都要考虑引入hashset/map, 而这道题之所以可以用hashset是因为，我们确保window区间里的char都是unique的
//Time O(2n), space O(min(m,n))
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
//more optimized for O(n) instead 2n, using HashMap
// i can skip to the repeated place instead skipping one by one
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
/*and when the charset is rather small, use int array instead of HashMap
int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII
*/
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
Minimum Window Substring
这里判断包含可以采用shash > thash的方式。这里的hashtable可以直接是一个256大小的数组（hash[t.charAt(i)]++可以直接这样给这个table赋值）。所以只要确保shash里面的值都比thash大即可
//O(ST)
public String minWindow(String s, String t) {
int lenS = s.length();
int j = 0;
String ans = "";
int len = Integer.MAX_VALUE;
int[] shash = new int[256];
int[] thash = new int[256];
for (int i = 0; i < t.length(); i++) {
thash[t.charAt(i)]++;
}
for (int i = 0; i < lenS; i++) {
while (j < lenS) {
if (valid(shash, thash)) {
break;
} else {
shash[s.charAt(j)]++;
j++;
}
}
if (valid(shash, thash)) { // 有可能遇到sLen < tLen
if (len > j - i) {
len = j - i;
ans = s.substring(i, j);
}
}
shash[s.charAt(i)]--;
}
return ans;
}
public boolean valid(int[] s, int[] t) {
for (int i = 0; i < t.length; i++) {
if (s[i] < t[i])
return false;
}
return true;
}
//optimization
//可以用counter来判断t中的每一个元素是否已经被covered 这样复杂度可以降为O(S+T)
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
// Dictionary which keeps a count of all the unique characters in t.
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
// Number of unique characters in t, which need to be present in the desired window.
int required = dictT.size();
// Left and Right pointer
int l = 0, r = 0;
// formed is used to keep track of how many unique characters in t
// are present in the current window in its desired frequency.
// e.g. if t is "AABC" then the window must have two A's, one B and one C.
// Thus formed would be = 3 when all these conditions are met.
int formed = 0;
// Dictionary which keeps a count of all the unique characters in the current window.
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
// ans list of the form (window length, left, right)
int[] ans = {-1, 0, 0};
while (r < s.length()) {
// Add one character from the right to the window
char c = s.charAt(r);
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
// If the frequency of the current character added equals to the
// desired count in t then increment the formed count by 1.
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
// Try and contract the window till the point where it ceases to be 'desirable'.
while (l <= r && formed == required) {
c = s.charAt(l);
// Save the smallest window until now.
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
// The character at the position pointed by the
// `Left` pointer is no longer a part of the window.
windowCounts.put(c, windowCounts.get(c) - 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
// Move the left pointer ahead, this would help to look for a new window.
l++;
}
// Keep expanding the window once we are done contracting.
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}