剑指 Offer 48. 最长不含重复字符的子字符串
解题思路：
滑动窗口法
- 当前字符在窗口中的索引为index
- 若当前字符在窗口中出现过，那么就将窗口中[0,index]区间的全部去除，从index+1开始新一轮的窗口
- 当前字符加入窗口
- 更新最大值
（indexOf谨慎用）
代码1：
const lengthOfLongestSubstring = s => {
// 滑动窗口
const window = [];
let max = 0;
const len = s.length;
for (let i = 0; i < len; i++) {
// 当前字符在窗口中的索引
const index = window.indexOf(s[i]);
if (index !== -1) {
// 当前字符在窗口中出现过，那么就将窗口中[0,index]区间的全部去除
// 从index+1开始新一轮的窗口
window.splice(0, index + 1);
}
// 当前字符加入窗口
window.push(s[i]);
// 更新最大值
if (max < window.length) max = window.length;
}
return max;
};
代码2：
const lengthOfLongestSubstring = s => {
let start=0,max=0
let res=new Set()
for(var end=0;end<s.length;end++){
if(!res.has(s[end])){
res.add(s[end])
}else{
max=Math.max(end-start,max)
while(res.has(s[end])){
res.delete(s[start])
start++
}
res.add(s[end])
}
}
max=Math.max(end-start,max)
return max
};
最长连续子字符串
解题思路：
连续子字符串跟不重复的不一样！！！！直接动态规划遍历存储！不要给相同的思路束缚了，踩坑了（一直debug发现想复杂了！T T），动态规划真香。。。。。。
踩坑代码：
function findLongestSubstr( str ) {
// write code here
let start=0,max=0
let res=[]
let i=0,j=0
if(str.length<=1)return str
str=str.split('')
for(var end=0;end<str.length;end++){
if(res.indexOf(str[end])!=-1||res.indexOf(str[end].toLowerCase())!=-1||res.indexOf(str[end].toUpperCase())!=-1){
res.push(str[end])
}else{
res.push(str[end])
if(end-start>max){
max=end-start
i=end
j=start
res.splice(0,max)
}
start=end
}
}
return str.slice(j,i).join('')
}
踩坑报错情况：
都9/11了！！！恶心吐了！！！！干嘛要想这么复杂啊我透！
代码：
function findLongestSubstr( str ) {
if(!str) return ""
let max=str[0]
let dp=[]
dp[0]=1
for(let i=1;i<str.length;i++){
if(str[i-1].toLowerCase()==str[i].toLowerCase()){
dp[i]=dp[i-1]+1
}else{
dp[i]=1
}
max=dp[i]>max.length?str.slice(i+1-dp[i],i+1):max
}
return max
}
module.exports = {
findLongestSubstr : findLongestSubstr
};
