1.无重复字符的最长子串（3 - 中/剑指48）
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 :
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：本题是面试的高频题目，也是hash表的一个具体应用。思路是维持一个队列（窗口），保持队列中的元素满足题目要求（元素不重复）。
具体实现是：使用hashmap记录每个字符的索引位置，便于更新下一个窗口的左边界，遍历字符串。
- 如果窗口中含有这个元素，移动移除左边界元素（左边索引+1）；
- 否则加入窗口，更新最长子串长度。
代码实现：
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (s == null || n == 0) {
return 0;
}
Map<Character, Integer> map = new HashMap<>();
int max = 0;
int left = 0;
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (map.containsKey(c)) {
left = Math.max(left, map.getOrDefault(c, 0) + 1);
}
map.put(c, i);
max = Math.max(max, i - left + 1);
}
return max;
}
2.串联所有单词的子串（30 - 难）
题目描述：给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意：子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 :
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
思路：由于单词长度固定，我们维护一个长度为所有元素长度总和的队列（窗口）。本题也是考察hash表，键为存储的单词，值存的单词出现的次数。具体实现见代码。注意：
-
可以用indexOf()，判断一个字符或者字符串是否存在一个字符串中，不存在返回负数；否则将这个单词加入哈希表；
-
当单词数组长度超过字符串长度，直接剔除。
-
对遍历的每一个窗口，用一个subMap记录，left和right记录左右边界（更新的话，是先将单词从字符串中截取出来，再在subMap中删除）；
-
通过移动右边界right，依次得到一个单词。如果wordMap中没有这个单词，更新左边界，清除这次记录（包括subMap和单词数量记录数count）；否则，加入subMap，注意count符合要求统计左边界，超过限制删除左边界。
代码实现：
public static List<Integer> solution2(String s, String[] words) {
List<Integer> res = new ArrayList<>();
Map<String, Integer> wordsMap = new HashMap<>();
if (s.length() == 0 || words.length == 0) return res;
for (String word: words) {
// 主串s中没有这个单词，直接返回空
if (s.indexOf(word) < 0) return res;
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
int oneLen = words[0].length(), wordsLen = oneLen * words.length;
if (wordsLen > s.length()) return res;
for (int i = 0; i < oneLen; ++i) {
int left = i, right = i, count = 0;
// 统计每个符合要求的word
Map<String, Integer> subMap = new HashMap<>();
// 右窗口不能超出主串长度
while (right + oneLen <= s.length()) {
// 得到一个单词
String word = s.substring(right, right + oneLen);
right += oneLen;
// words[]中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面
if (!wordsMap.containsKey(word)) {
left = right;
subMap.clear();
count = 0;
} else {
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
++count;
// 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串
// 如 ["foo","bar","foo","the"] "| foobarfoobar| foothe"
// 第二个bar虽然是words[]中的单词，但是次数抄了，那么右移一个单词长度后 "|barfoobarfoo|the"
// bar还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的bar和它之前的单词(串)全移出去
while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
// 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一)
String w = s.substring(left, left + oneLen);
subMap.put(w, subMap.getOrDefault(w, 0) - 1);
// 符合的单词数减一
--count;
// 左窗口位置右移
left += oneLen;
}
// 当前窗口字符串满足要求
if (count == words.length) res.add(left);
}
}
}
return res;
}
3.最小覆盖子串（76 - 难）
题目描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。要求：时间复杂度O(N)。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案，两个字符串只含有英文字符。
示例 :
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
思路：可以通过滑动窗口解决，注意：最小覆盖子串长度不唯一，但至少与t相同。我们可以定义两个变量：start（最小覆盖子串的起始位置），size（最小覆盖子串的长度）
关键：如何判断窗口中含有t的所有元素？可以使用数组或者哈希表记录字符出现的次数。
-
使用数组记录t中（我们需要寻找的）字符的个数，cnt记录要找字符总数。
-
当我们遍历s字符串时，遇到需要的字符我们就将他出现的次数 - 1。总次数cnt == 0，此时找到一个覆盖子串。
-
上述还不是一次寻找的最小覆盖子串，需要找左边界，如何找呢？还是通过出现的次数，方法：在遍历过程中，s中出现每个的字符在need数组中-1，这样我们在找左边界是为负数，一定要恢复！
-
这时，可以统计长度size，更新起始索引start；
-
最终，移动窗口，如何移动（删除左边界元素）呢？将其加入need数组，更新左边界和cnt个数 + 1，下次遍历出现这个字符就可以删除（也可以理解为替换）。
代码实现：
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()) {
return "";
}
// 记录需要字符的个数
int[] need = new int[128];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
int left = 0;
int size = Integer.MAX_VALUE, cnt = t.length();
int start = 0;
for (int i = 0; i < s.length(); i++) {
if (need[s.charAt(i)] > 0) cnt--;
need[s.charAt(i)]--;
// 窗口中已经包含所有需要的字符
if (cnt == 0) {
while (left < i && need[s.charAt(left)] < 0) {
need[s.charAt(left)]++;
left++;
}
if (i - left + 1 < size) {
size = i - left + 1;
start = left;
}
// 窗口移动，注意更新need数组和cnt值
need[s.charAt(left)]++;
left++;
cnt++;
}
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
4.找到字符串中所有字母的异位词（438 - 中）
题目描述：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 :
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
思路：显然滑窗，窗口大小为p字符串的长度，关键：那么如何比较两部分的元素是否是异位词呢？
-
可以直接调库函数
Arrays.equals()，判断两个字符串是否是异位词（即两个数组是否相同）。 -
本题仍使用数组存储字符出现次数，但是本题两个串申请了两个空间，方便进行上边的对比。
-
这里判断与上题相比简单了许多，只要长度满足我们就进行判断，两部分异构，记录起始索引；否则，移除左边界，这里直接在sMap删除。
代码实现：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
if (s.length() < p.length()) return ans;
int[] pMap = new int[26];
for (int i = 0; i < p.length(); i++) {
pMap[p.charAt(i) - 'a']++;
}
int[] sMap = new int[26];
int left = 0;
for (int i = 0; i < s.length(); i++) {
sMap[s.charAt(i) - 'a']++;
if (i - left + 1 == p.length()) {
if (Arrays.equals(sMap, pMap)) {
ans.add(left);
}
sMap[s.charAt(left) - 'a']--;
left++;
}
}
return ans;
}
5.至多包含两个不同字符的最长子串（159 - 中）
题目描述：给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。
示例 :
示例 1:
输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。
示例 2:
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。
思路：维护一个窗口，元素类型至多两种。本题关键：如何判断窗口中的元素类型大于2了呢？
这里使用Hashmap记录当前字符在窗口中最靠右的索引值，为什么这么做呢？这样我们可以控制窗口的移动，right每右移一步：
-
若已经存在，更新map中当前元素最靠右的位置
-
若不存在，添加到map唯一存在，索引也是最靠右的
这样就好办了，如果我们元素类型超了2，即map的大小等于3。
-
记录最小索引值，用于下边删除和更新左边界。
-
删除操作是删除索引最小的那些或那个元素，因为记录的是右边界，这样我们也不用担心左边界问题。
代码实现：
public int lengthOfLongestSubstringTwoDistinct(String s) {
int strLength = s.length();
if (strLength < 3) return strLength;
int left = 0, right = 0;
HashMap<Character, Integer> map = new HashMap<>();
int maxLen = 2;
while (right < strLength) {
map.put(s.charAt(right), right);
right++;
if (map.size() == 3) {
int minIdx = Collections.min(map.values());
map.remove(s.charAt(minIdx));
left = minIdx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
-
ps：map.values()显示map中所有的值，返回值类型Collection<Integer>，用min()获取最小值。
-
map.remove(key)：删除map中键为key的元素
6.至多包含k个不同字符的最长子串（340 - 难）
题目描述：给定一个字符串 s ，找出 至多 包含k个不同字符的最长子串 t ，并返回该子串的长度。
示例 :
示例 1:
输入: "eceba" 2
输出: 3
解释: t 是 "ece"，长度为3。
示例 2:
输入: "aa", 1
输出: 2
解释: t 是 "aa"，长度为2。
思路：维护一个窗口，元素类型至多k种。具体实现：类比上一题，解决方案还是使用hash表记录字符出现的最右索引。
代码实现：
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int strLength = s.length();
if (strLength < k + 1) return strLength;
if (strLength * k == 0) return 0;
int left = 0, right = 0;
HashMap<Character, Integer> map = new HashMap<>();
int maxLen = k;
while (right < strLength) {
map.put(s.charAt(right), right);
right++;
if (map.size() == k + 1) {
int minIdx = Collections.min(map.values());
map.remove(s.charAt(minIdx));
left = minIdx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
7.替换后最长重复字符（424 - 中）
题目描述：给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
示例 :
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
思路：可以想一下k = 0的情况（不替换字符），即求字符串的最长重复元素。关键点：如何判断一个字符串改变了k个字符就变成了一条连续的子串？
只要保证【当前子串的长度 <= 当前子串出现字符最多的个数 + k】，这样一定可以将当前子串替换为一条连续的子串（元素都相同）。
-
当满足上述条件，右边界扩张，并更新之前出现重复字母的最多个数（这个个数用一个数组记录）；
-
一旦不满足上述条件，我们移除左边界（直接在数组中将左边界对应的次数 - 1）；
注意：我们窗口维护了可能的最长子串，所以返回值为窗口大小，即s.length() - left。
代码实现：
public int characterReplacement(String s, int k) {
int n = s.length();
if (s == null || n < 2 || n < k) return n;
int[] map = new int[26];
int left = 0;
int ans = 0, preMax = 0;
for (int i = 0; i < n; i++) {
int index = s.charAt(i) - 'A';
map[index]++;
preMax = Math.max(preMax, map[index]);
if (i - left + 1 > preMax + k) {
map[s.charAt(left) - 'A']--;
left++;
}
}
return n - left;
}
网友评论