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

链接：3.无重复字符的最长子串
难度：Medium
标签：哈希表、字符串、滑动窗口
简介：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

题解 1 - javascript

• 编辑时间：2019-09-20
• 执行用时：128ms
• 内存消耗：37.1MB
• 编程语言：javascript
• 解法介绍：创建数组，遍历每个字符，若字符不存在数组中则压栈，若字符存在则循环出栈直到字符不存在，每次遍历的最后判断数组长度大于 length 长度，则赋值给 length。

var lengthOfLongestSubstring = function (s) {
  let arr = [],
    length = 0;
  for (let c of s) {
    if (arr.indexOf(c) > -1) {
      while (arr.indexOf(c) > -1) {
        arr.shift();
      }
    }
    arr.push(c);
    if (arr.length > length) {
      length = arr.length;
    }
  }
  return length;
};

题解 2 - typescript

• 编辑时间：2021-10-16
• 执行用时：180ms
• 内存消耗：47.7MB
• 编程语言：typescript
• 解法介绍：二分。

function lengthOfLongestSubstring(s: string): number {
  if (s.length === 0) return 0;
  let min = 1;
  let max = s.length;
  while (min < max) {
    const mid = (min + max + 1) >> 1;
    if (check(mid)) min = mid;
    else max = mid - 1;
  }
  return min;
  function check(len: number): boolean {
    const map: Record<string, number> = {};
    let ans = 0;
    for (let i = 0; s[i]; i++) {
      if (!map[s[i]]) ans++;
      map[s[i]] = (map[s[i]] ?? 0) + 1;
      if (i >= len) {
        map[s[i - len]]--;
        if (map[s[i - len]] === 0) ans--;
      }
      if (ans === len) return true;
    }
    return false;
  }
}

题解 3 - c

• 编辑时间：2021-11-30
• 执行用时：4ms
• 内存消耗：5.7MB
• 编程语言：c
• 解法介绍：滑动窗口判断当前窗口中是否存在超过两次的字符，存在则左侧右移，否则右侧右移。

int lengthOfLongestSubstring(char * s){
    int arr[128] = {0};
    int cnt = 0, l = 0, r = 0, n = strlen(s), ans = 0;
    while (r < n) {
        while (r < n && cnt == 0) {
            arr[s[r]] += 1;
            if (arr[s[r]] == 2) {
                ++cnt;
            }
            ++r;
            if (cnt == 0 && ans < r - l) ans = r - l;
        }
        while (cnt != 0) {
            arr[s[l]] -= 1;
            if (arr[s[l]] == 1) --cnt;
            ++l;
        }
    }
    return ans;
}

题解 4 - cpp

• 编辑时间：2021-12-24
• 执行用时：4ms
• 内存消耗：6.7MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
          public:
    int lengthOfLongestSubstring(string s) {
        int arr[200] = {0}, l = 0, r = 0, ans = 0, n = s.size();
        while (r < n) {
            while (r < n && arr[s[r]] < 1) arr[s[r++]]++;
            ans = max(ans, r - l);
            char ch = s[r++];
            arr[ch]++;
            while (s[l] != ch) arr[s[l++]]--;
            arr[s[l++]]--;
        }
        return ans;
    }
};