Su‌‌‌‌‌‌‍‍‌‍‍‌‌‍‌‍‌‍‌‌‍‌‌‍‍‍‍‌‍‍‍‌barray + sliding window类型总结

SubString + Sliding window 类题型

借用Map的解法

第一类：找尽量不重复的最大substring /substring个数

3. Longest Substring Without Repeating Characters

常见是Set的解法，Discussion里面有说就不写在这里了。

Map方法：一旦map中有当前char且比慢指针 i 更后面就要更新慢指针 i

代码如下：

public int lengthOfLongestSubstring(String s) {

if (s == null || s.length() == 0) return 0;

int result = 0;

Map<Character, Integer> map = new HashMap<>();

for (int i = 0, j = 0; j < s.length(); j++) {

char c = s.charAt(j);

if (map.containsKey(c) && map.get(c) >= i) {

i = map.get(c);

i++;

}

result = Math.max(result, j - i + 1);

map.put(c, j);

}

return result;

}

第二类：找尽量重复的最大substring/substring个数

159. Longest Substring with At Most Two Distinct Characters

340. Longest Substring with At Most K Distinct Characters

992. Subarrays with K Different Integers

这三题可以用同一个模版解，模版是340题答案，最多K个不同字符的最大subarray长度。

其中992题虽然问的是正好K个不同字符，但实际只要用（最多K个 - 最多K-1个）就可以了，也就是return 模版(A, K) - 模版(A, K - 1);这里只要改input类型。

如果是要求substring个数（992），只需要把res = Math.max(res, i - start + 1)更改为res += j - i + 1就可以了。

模版如下：

public int lengthOfLongestSubstringKDistinct(String s, int k) { if (s == null || s.length() == 0) return 0;

HashMap<Character, Integer> map = new HashMap<>();

int start = 0;

int res = 0;

for(int i = 0; i < s.length(); i++) {

map.put(s.charAt(i), i);

if (map.size() > k) {

int leftMost = s.length();

for (int num : map.values()) {

leftMost = Math.min(leftMost, num);

}

map.remove(s.charAt(leftMost));

start = leftMost + 1;

} else {

res = Math.max(res, i - start + 1);

}

}

return res;

}

每次移除尽可能短的字符，使得剩下的subarray (i 到 j) 字符数目不超过K

我觉得这种模版其实类似固定大小为K的最小堆 min priority heap, 只不过元素是map, 每次加入新元素后，如果map size大于K了，就pop出一个value最小的map.