无重复字符的最长子串js
时间: 2024-09-29 12:16:07 浏览: 19
在JavaScript中,给定一个字符串,寻找其中不包含重复字符的最长连续子串是一个常见的问题,可以使用滑动窗口算法来解决。以下是简单的解决方案:
```javascript
function lengthOfLongestSubstring(s) {
let maxLength = 0;
let start = 0;
const charMap = {};
for (let end = 0; end < s.length; end++) {
if (charMap[s[end]]) {
// 如果当前字符已经在map中,说明之前的位置有重复字符
start = Math.max(start, charMap[s[end]] + 1);
}
// 更新最长子串长度和新的字符位置
maxLength = Math.max(maxLength, end - start + 1);
charMap[s[end]] = end; // 将当前字符及其位置存入map
}
return maxLength;
}
```
这个函数通过维护一个`start`和`end`指针以及一个哈希表`charMap`来跟踪子串。当遇到重复字符时,移动`start`指针直到该字符不在子串范围内,然后继续更新最长子串的长度。
相关问题
求字符串的最长不重复子串JS
在JavaScript中,求一个字符串的最长无重复字符子串通常可以使用滑动窗口或哈希集合的方式来解决。这里是一个基于哈希集合的解决方案:
```javascript
function lengthOfLongestSubstring(s) {
let maxLength = 0;
let seen = {};
let left = 0;
for (let right = 0; right < s.length; right++) {
if (seen[s[right]]) {
left = Math.max(left, seen[s[right]] + 1);
}
maxLength = Math.max(maxLength, right - left + 1);
seen[s[right]] = right;
}
return maxLength;
}
```
这个函数的工作原理是维护一个左边界`left`和右边界`right`,并在每个位置检查从`left`到当前位置是否有重复字符。如果有,移动左边界`left`到重复字符的下一个位置。同时更新最长子串的长度`maxLength`。
说明:给定一个字符串,找出不含有重复字符的最长子串值及长度值 如给定'abcabcbb' ,没有重复字符的最长子串值是'abc' ,最长长度值是3。用JavaScript解答
可以用滑动窗口(双指针)的方法来解决这个问题。
具体思路是:用一个指针指向子串的开始位置,另一个指针不断向后移动寻找最长子串。每次移动右指针时,判断右指针所指的字符是否在子串中出现过,若出现过,就将左指针向右移动,直到子串中不包含右指针所指的字符为止。
代码如下:
```javascript
function lengthOfLongestSubstring(s) {
let left = 0, right = 0;
let maxLen = 0;
let set = new Set();
while (right < s.length) {
if (!set.has(s.charAt(right))) {
set.add(s.charAt(right));
right++;
maxLen = Math.max(maxLen, set.size);
} else {
set.delete(s.charAt(left));
left++;
}
}
return maxLen;
}
```
其中,`set` 用于存储当前子串中出现过的字符,`left` 和 `right` 分别指向子串的左右边界,`maxLen` 保存最长的子串长度。
时间复杂度为 $O(n)$,空间复杂度为 $O(min(n, m))$,其中 $n$ 是字符串长度,$m$ 是字符集的大小。