JavaScript代码-求不含重复字符的最长子串长度
5星
- 浏览量: 0
- 大小:None
- 文件类型：ZIP
简介：
本段代码提供了一个方法来解决编程中的经典问题——寻找给定字符串中不含重复字符的最长子字符串。通过巧妙运用滑动窗口技术或哈希表，能够高效地计算出目标子串的长度，适用于各种前端和后端场景，助力开发者提高算法实现能力。
在JavaScript编程中处理字符串问题以及应用滑动窗口算法是常见的任务类型，通常出现在编程面试或在线挑战中。这类题目要求找到给定字符串中最长的子串，并且这个子串中的所有字符都不重复。
要解决这个问题，我们可以使用哈希表（HashMap）和两个指针的方法，这被称为“滑动窗口”方法。理解这一概念很重要：滑动窗口是在数组或字符串中定义的一个连续子集，其左右边界可以在数据结构的范围内移动。在这个问题里，我们的左指针表示子串的起始位置，右指针表示结束位置。我们通过增加右指针来扩展子串，并使用哈希表检查新添加字符是否已存在于当前子串中。如果存在重复，则将左指针向右移一位并继续操作；每次更新最长无重复字串长度。
以下是解决问题的步骤：
1. 初始化两个指针，left和right，初始值为0，以及一个用于存储子串内字符及其出现次数的哈希表。
2. 定义一个变量maxLen来记录最长时间内的无重复字符子串长度，并将其初始化为0。
3. 使用while循环，条件是右指针不超过字符串长度：
- 在每次迭代中检查当前right指向的字符是否已在哈希表内。如果不在，则添加到哈希表并更新最大长度（maxLen = Math.max(maxLen, right - left + 1)）。
- 如果存在重复字符，减少左指针位置处字符计数，并在必要时从哈希表中移除该键值对；同时将left向右移动一位以排除重复字符的影响。
4. 循环结束后返回maxLen作为最长无重复子串的长度。
示例代码如下：
```javascript
function slidingWindowWithoutDuplicates(str) {
let left = 0, right = 0;
let maxLen = 0;
const charMap = new Map();
while (right < str.length) {
const currentChar = str[right];
if (!charMap.has(currentChar)) {
charMap.set(currentChar, 1);
maxLen = Math.max(maxLen, right - left + 1);
} else {
charMap.set(currentChar, charMap.get(currentChar) + 1);
while (charMap.get(currentChar) > 1) {
charMap.set(str[left], charMap.get(str[left]) - 1);
if (charMap.get(str[left]) === 0) {
charMap.delete(str[left]);
}
left++;
}
}
right++;
}
return maxLen;
}
console.log(slidingWindowWithoutDuplicates(abcabcbb)); // 输出：3，最长子串为 abc
```
通过这种方法可以有效地找出给定字符串中最长的不包含重复字符的子串，并计算其长度。这不仅考察了对字符串处理的理解，还涉及到了哈希表和滑动窗口这两种重要的数据结构和算法思想的应用。
全部评论 (0)
