Skip to content

3. 无重复字符的最长子串

3. 无重复字符的最长子串

解法一: 线性法

  • 快慢指针线性扫描
  • i 是慢指针，j 是快指针
  • 当 j 遇到一个重复出现的字符时，该字符在 i, j 之间的 found 位置
  • 慢指针 i，跳到 found + 1 处，继续扫描
class Solution {
  public:
  int lengthOfLongestSubstring(string s) {
    int len = s.length();
    if (len <= 1) return len;

    int i = 0, j = 1, maxLen = 1, curLen = 1, found = -1;

    while (j < s.len)) {
      found = s.substr(i, curLen).find(s[j]);
      if (found < 0 ) {
        j++;
        curLen++;
        maxLen = curLen > maxLen ? curLen : maxLen;
      } else {
        i += found + 1;
        curLen -= found + 1;
      }
    }

    return maxLen;
  }
};

解法二: 利用 Set 判重

  • 定义集合 set；
  • 从给定字符串的头开始，每次检查当前字符是否在集合内；
  • 如果不在，说明该字符不会造成重复和冲突，加入集合，并统计集合长度，或为最长子串；
  • 定义快慢指针：i 是慢指针，j 是快指针；
  • 当 j 遇到一个重复出现的字符时，从慢指针开始一个一个将 i 指针指向的字符从集合里删除
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const len = s.length
  if (len <= 1) {
    return len;
  }

  let max = 1;
  let i = 0, j = 0; //  快慢指针
  let set = new Set();

  while(j < len) {
    while (set.has(s[j])) {
      set.delete(s[i++]);
    }

    set.add(s[j++]);
    max = max < set.size ? set.size : max;
  }

  return max;
};
  • 快指针添加到 set，慢指针从 set 删除，每次操作set 时间复杂度 O(1)
  • 时间复杂度：字符串最多遍历两遍 n * O(1) + n * O(1) = O(n)
  • 空间复杂度：O(n)

解法三: HashMap 优化

  • 利用 hash 表记录下标
  • 每次遇到重复字符，下标记为 found，慢指针移动到 found + 1
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let len = s.length;
  if (len <= 1) {
    return len;
  }

  let max = 0;
  let i = 0, j = 0;
  let map = {}; // 记录下标

  while (j < len) {
    let found = map[s[j]];
    if (found !== undefined && found >= i) {
      i = found + 1;
    }

    map[s[j]] = j;
    j++;
    max = max < j - i ? j - i : max;
  }

  return max;
}