#438号题疑问
来源:3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
慕粉4283821
2021-01-04
// JS相关实现
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function(s, p) {
var needMap = {}; // 实际需要的hashMap
for(var i = 0; i < p.length; i++) {
needMap[p[i]] ? needMap[p[i]]++ : needMap[p[i]] = 1;
}
var needLen = Object.keys(needMap).length;
var realMap = {}; // 窗口的hashmap
var res = [];
var l = 0, r = 0;
var matchCount = 0; // 匹配到的字母总个数
while(r < s.length) {
var cur = s[r];
// 当前元素 是 需要的元素
if(needMap[cur]) {
// 窗口map 计数
realMap[cur] ? realMap[cur]++ : (realMap[cur] = 1);
// 如果数量相等了,匹配到的个数就 +1
if(needMap[cur] === realMap[cur]) {
matchCount++;
}
}
r++;
while(matchCount === needLen) {
var leftItem = s[l];
if((r - l) === p.length) {
res.push(l);
}
if(needMap[leftItem] && realMap[leftItem]) {
realMap[leftItem]--;
if(realMap[leftItem] < needMap[leftItem]) {
matchCount--;
}
}
l++;
}
}
return res;
};
老师,关于这题我有个疑问,我们在记录窗口中的字母个数时, 遇到是我们需要的字母 就会计数, 那如果碰到了 其他字母 却没有重置map, 是因为 我们这里考虑的子串 是 不一定要连续的吗? 在官方题目描述上没有看到关于这块的描述。
写回答
1回答
-
liuyubobobo
2021-01-04
考虑的子串是连续的。正是因为没有重置,整个算法才能是线性的。
if((r - l) === p.length) 这个判断,保证了不仅仅在这个子串中,所有的字母都出现了,而且肯定没有多余的字符。
设想一个你认为可能出问题的测试用例,比如存在一个不连续的子串,除了给定的字符,还有多余字符,运行你的程序,看一看是否会出问题?如果没有出问题,单步跟踪一下,看看这个程序为什么能躲过你设想的问题?
进步就在这个过程中哦。
继续加油!:)
012021-01-04
相似问题