[3] 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
分析：
a b c a b c b b
|a b c a b c b b
↑ left=0,maxlen=1 窗口范围 [a]
a |b c a b c b b
↑ left=0,maxlen=2 窗口范围 [ab]
a b |c a b c b b
↑ left=0,maxlen=3 窗口范围 [abc]
a b c |a b c b b
↑ left=1,maxlen=3 窗口范围 [bca]
代码：
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int maxlen = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
left = Math.max(left, map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i), i);
maxlen = Math.max(maxlen, i - left + 1);
}
return maxlen;
}
[30] 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
例如，如果 words = ["ab","cd","ef"]， 那么 abcdef、abefcd、cdabef、cdefab、efabcd、efcdab 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
分析：
>>> barfoothefoobarman
1、单词个数m=6，长度n=3，字符串长度ls=18
2、按照长度(n=3)的维度进行遍历
bar foo the foo bar man
1) [barfoo] = bar foo
[foothe] = foo the ...
2) [arfoot] = arf oot
[oothef] = oot hef ...
3) [rfooth] = rfo oth
[othefo] = oth efo ...
3、Map<String, Integer> differ
出现在窗口中的单词，每出现一次，则+1。
出现在words中的单词，每出现一次，则-1。如果value为0，则移除。
4、窗口右移。窗口移动时，若出现 \textit{differ}differ 中值不为 00 的键的数量为 00，则表示这个窗口中的单词频次和 words 中单词频次相同，窗口的左端点是一个待求的起始位置。
代码：
public static List<Integer> findSubstring2(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int m = words.length;
int n = words[0].length();
int ls = s.length();
for (int i = 0; i < n; i++) {// 即不同的起始位置
if (i + n * m > ls) {// 长度不足直接退出循环
break;
}
Map<String, Integer> differ = new HashMap<>();
// 在窗口范围内统计
for (int j = 0; j < m; j++) {
// 窗口范围内截取单词
String word = s.substring(i + j * n, i + (j + 1) * n);
differ.put(word, differ.getOrDefault(word, 0) + 1);
}
for (String word : words) {
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (0 == differ.get(word)) {
differ.remove(word);
}
}
for (int start = i; start < ls - m * n + 1; start += n) {
if (start != i) {
// 右侧移入n，新进入的单词
String word = s.substring(start + (m - 1) * n, start + m * n);
differ.put(word, differ.getOrDefault(word, 0) + 1);
if (0 == differ.get(word)) {
differ.remove(word);
}
// 左侧移除n，移除的单词
word = s.substring(start - n, start);
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
if (differ.isEmpty()) {
res.add(start);
}
}
}
return res;
}
[76] 最小覆盖子串
评论