当前位置：首页 > article >正文

前端算法题

article 2024/11/23 3:57:29

js做算法题-无重复字符的最长子串求最长不重复字串

要找到一个字符串中无重复字符的最长子串，我们可以使用滑动窗口（Sliding Window）算法。这种方法通过维护一个窗口来追踪当前的子串，并利用一个集合来检查字符是否重复。

算法步骤

使用两个指针 start 和 end 来表示当前窗口的范围。
使用一个集合 charSet 来存储当前窗口中的字符。
初始化 maxLength 变量来记录最长子串的长度。
遍历字符串，逐个扩展 end 指针：
- 如果字符不在 charSet 中，添加它并更新 maxLength。
- 如果字符已经存在，移动 start 指针，直到窗口中的字符不再重复。
返回 maxLength。

function lengthOfLongestSubstring(s) {
  let charSet = new Set(); // 用于存储当前窗口中的字符
  let maxLength = 0;       // 最长子串的长度
  let start = 0;           // 窗口的起始指针

  for (let end = 0; end < s.length; end++) {
    // 如果字符已经存在于集合中，移动 start 指针
    while (charSet.has(s[end])) {
      charSet.delete(s[start]); // 从集合中移除 start 指向的字符
      start++;                   // 移动 start 指针
    }
    charSet.add(s[end]);         // 添加当前字符到集合中
    maxLength = Math.max(maxLength, end - start + 1); // 更新最长子串的长度
  }

  return maxLength; // 返回最长子串的长度
}

// 示例用法
const input = "abcabcbb";
console.log(lengthOfLongestSubstring(input)); // 输出: 3

查看全文

http://www.kler.cn/a/403228.html