JavaScript-Algorithms
JavaScript-Algorithms copied to clipboard
Published
20 hours ago •
sisterAn
sisterAn
字节&Leetcode3：无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
附leetcode：leetcode
对原数组进行判断，是否在arr里 如果在就将arr字符串之前的全部去除，不在就直接push，最后判断长度
var lengthOfLongestSubstring = function(s) {
let arr = [];
let length = 0;
for(let item of s){
if(arr.includes(item)){
let index = arr.indexOf(item);
arr.splice(0,index+1);
}
arr.push(item);
length = length > arr.length ? length : arr.length;
}
return length;
};
快慢指针维护一个滑动窗口，如果滑动窗口里面有快指针fastp所指向的元素（记录这重复元素在滑动窗口的索引tmp），那么滑动窗口要缩小，即慢指针slowp要移动到tmp的后一个元素。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let res = 0, slowp = 0, tmp = 0
for(let fastp = 0; fastp < s.length; fastp++) {
tmp = s.substring(slowp,fastp).indexOf(s.charAt(fastp)) // 滑动窗口有没有重复元素
if(tmp === -1) { // 没有
res = Math.max(res, fastp-slowp+1) // 上一次值和滑动窗口值大小比较
}else{ // 有，移动慢指针， 是slowp+tmp+1不是tmp+1，因为tmp是根据滑动窗口算的
slowp = slowp + tmp + 1
}
}
return res
};
细节： 快指针也要从0开始，如果从1开始，类似'aaaa'，结果就是0，因为tmp永远不等于-1
方法一：悬浮框圈出满足条件的字符串，时间复杂度O(n),空间复杂度O(n),
/**
* @param {string} str
* @return {number}
*/
function lengthOfLongestSubstring(str){
if(!str || str.length < 0) return 0;
let num = 0;
let strArr = str.split('');
let lengthOfSubstring = [];
for(let i = 0; i < strArr.length; i ++){
const index = lengthOfSubstring.indexOf(strArr[i])
if( index <0 ){
lengthOfSubstring.push(strArr[i])
}else{
lengthOfSubstring = lengthOfSubstring.splice(index+1)
lengthOfSubstring.push(strArr[i])
}
num = num<lengthOfSubstring.length?lengthOfSubstring.length:num
}
return num;
}
方法二：双悬浮框从字符串首尾圈出满足条件的字符串，直到重合，时间复杂度O(n/2),空间复杂度O(n),
/**
* @param {string} str
* @return {number}
*/
function lengthOfLongestSubstring(str){
if(!str || str.length < 0) return 0;
let num = 0;
let strArr = str.split('');
let lengthOfStartSubstring = [];
let lengthOfEndSubstring = [];
let loopTime = strArr.length - 1
for(let i = 0; i <= loopTime; i ++){
const startIndex = lengthOfStartSubstring.indexOf(strArr[i])
const endIndex = lengthOfEndSubstring.indexOf(strArr[loopTime-i])
if( startIndex <0 ){
lengthOfStartSubstring.push(strArr[i])
}else{
lengthOfStartSubstring = lengthOfStartSubstring.splice(startIndex+1)
lengthOfStartSubstring.push(strArr[i])
}
if( endIndex <0 ){
lengthOfEndSubstring.push(strArr[ loopTime-i])
}else{
lengthOfEndSubstring = lengthOfEndSubstring.splice(endIndex+1)
lengthOfEndSubstring.push(strArr[loopTime-i])
}
console.log(lengthOfStartSubstring, lengthOfEndSubstring)
let lengthOfSubstring = lengthOfStartSubstring.length>lengthOfEndSubstring.length?lengthOfStartSubstring.length:lengthOfEndSubstring.length
num = num<lengthOfSubstring?lengthOfSubstring:num
console.log(i)
if(2*i - loopTime >= lengthOfStartSubstring.length) return;
}
return num;
}
解法一：维护数组
解题思路： 使用一个数组来维护滑动窗口
遍历字符串，判断字符是否在滑动窗口数组里
- 不在则
push进数组 - 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符
push进数组 - 然后将
max更新为当前最长子串的长度
遍历完，返回 max 即可
画图帮助理解一下：
代码实现：
var lengthOfLongestSubstring = function(s) {
let arr = [], max = 0
for(let i = 0; i < s.length; i++) {
let index = arr.indexOf(s[i])
if(index !== -1) {
arr.splice(0, index+1);
}
arr.push(s.charAt(i))
max = Math.max(arr.length, max)
}
return max
};
时间复杂度：O(n2)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)
空间复杂度：O(n)
解法二：维护下标
解题思路： 使用下标来维护滑动窗口
代码实现：
var lengthOfLongestSubstring = function(s) {
let index = 0, max = 0
for(let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s[j])
if(index !== -1) {
i = i + index + 1
}
max = Math.max(max, j - i + 1)
}
return max
};
时间复杂度：O(n2)
空间复杂度：O(n)
解法三：优化的Map
解题思路：
使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标
使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标
遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中
最后，返回 max 即可
代码实现：
var lengthOfLongestSubstring = function(s) {
let map = new Map(), max = 0
for(let i = 0, j = 0; j < s.length; j++) {
if(map.has(s[j])) {
i = Math.max(map.get(s[j]) + 1, i)
}
max = Math.max(max, j - i + 1)
map.set(s[j], j)
}
return max
};
时间复杂度：O(n)
空间复杂度：O(n)
function getMaxLen(str) { var maxLen = 0, startIndex = 0; for(var i = 0; i < str.length; i++) { for(var j = startIndex; j < i; j++) { if (str[j] === str[i]){ startIndex = j + 1; break } } maxLen = Math.max(maxLen, i - startIndex + 1); } return maxLen; }
经典的滑动窗口算法题
var lengthOfLongestSubstring = function (s) {
if (s.length < 2) {
return s.length;
}
let window = new Map();
let left = 0;
let right = 0;
let res = 0;
while (right < s.length) {
let rc = s[right];
right++;
if (window.has(rc)) {
window.set(rc, window.get(rc) + 1);
} else {
window.set(rc, 1);
}
while (window.get(rc) > 1) {
let lc = s[left];
left++;
if (window.has(lc)) {
window.set(lc, window.get(lc) - 1);
}
}
res = Math.max(res, right - left);
}
return res;
};
var lengthOfLongestSubstring = function(s) {
let max = 0
let map = {}
let start = 0
let end
for (let i = 0; i < s.length; i++) {
if (map[s[i]] >= 0) {
start = map[s[i]] + 1
}
map[s[i]] = i
end = i
Object.keys(map).forEach(c => {
if (map[c] < start) {
map[c] = -1
}
})
if (max < (end - start + 1)) {
max = end - start + 1
}
}
return max
};
代码中的 res 变量存储的是所有不重复子串及其长度，就本题目完全可以不需要这个变量，如果题目需要返回不重复子串则可以用到
var lengthOfLongestSubstring = function (str) {
if (!str) return 0
let res = {} // 存储所有不重复子串
let max = 0
let s = ''
for (const char of str) {
let idx = s.indexOf(char)
s += char
if (idx === -1) { // 不重复
res[s] = s.length // 存储不重复子串
max = Math.max(max, s.length)
} else { // 重复，从重复的字符的第一个个位置进行分割
let del = s.slice(0, idx + 1)
res[del] = del.length // 存储不重复子串
max = Math.max(max, del.length)
s = s.slice(idx + 1)
res[s] = s.length // 存储不重复子串
max = Math.max(max, s.length)
}
}
res[s] = s.length
max = Math.max(max, s.length)
return max
}
悬浮窗
var lengthOfLongestSubstring = function (s) {
let next = 0;
let start = 0;
let arr = [];
let len = 0;
while (true) {
if (arr.includes(s[next])) {
arr = [];
start++;
next = start;
if (start === s.length - 1) {
return len;
break;
}
} else {
if (s[next]) {
arr.push(s[next]);
next++;
} else {
return len;
break;
}
}
len = arr.length > len ? arr.length : len;
}
};
利用了 Map 存储已经存放的char
const lengthOfLongestSubstring = (source: string) => {
if (source.length <= 1) return source.length;
let i = 0;
let map: Record<string, boolean> = {};
let count = 0;
let maxCount = 0;
while (i < source.length) {
const char = source.charAt(i);
if (!map[char]) {
count++;
map[char] = true;
i++;
continue;
}
if (maxCount < count) {
maxCount = count;
}
map = {}; count = 0;
}
return maxCount;
};
let lengthOfLongestSubstring(str) {
//对原数组进行判断，是否在arr里 如果在就将arr字符串之前的全部去除，不在就直接push，最后判断长度
let arr = []
let length = 0
for (let m of str) {
if (arr.includes(m)) {
let index = arr.indexOf(m)
arr.splice(0, index + 1);
}
arr.push(m);
length = Math.max(arr.length, length)
}
return length
}
function getMostNoRepeatChar(str){
let obj = {}
let maxLen = 0
let curCount = 0
for (let i=0;i<str.length;i++){
if(obj.hasOwnProperty(str.charAt(i))){
maxLen = curCount>maxLen?curCount:maxLen
curCount = 0
obj={}
i--
}else{
obj[str.charAt(i)] = true
curCount++
}
}
return maxLen
}
console.log(getMostNoRepeatChar('abcabcbb'))
console.log(getMostNoRepeatChar('bbbbb'))
console.log(getMostNoRepeatChar('pwwkew'))
