## 题目地址

https://leetcode.com/problems/longest-substring-without-repeating-characters/

## 题目描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

``````Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

``````

Example 2:

``````Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

``````

Example 3:

``````Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a _subsequence_ and not a substring.
``````

## 思路

### 思路2

（1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；

（2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；

（3）重复（1）（2），直到左边索引无法再移动；

（4）维护一个结果res，每次用出现过的窗口大小来更新结果res，最后返回res获取结果。

## 关键点解析

1. 用一个mapper记录出现过并且没有被删除的字符
2. 用一个滑动窗口记录当前index开始的最大的不重复的字符序列
3. 用res去记录目前位置最大的长度，每次滑动窗口更新就去决定是否需要更新res

## 代码

C++ 解法一：

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = -1, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};

``````

C++ 解法二：

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(128, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};

``````

Java 解法二：

``````public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] m = new int[256];
Arrays.fill(m, -1);
int res = 0, left = -1;
for (int i = 0; i < s.length(); ++i) {
left = Math.max(left, m[s.charAt(i)]);
m[s.charAt(i)] = i;
res = Math.max(res, i - left);
}
return res;
}
}

``````

C++ 解法三：

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = 0, i = 0, n = s.size();
unordered_set<char> t;
while (i < n) {
if (!t.count(s[i])) {
t.insert(s[i++]);
res = max(res, (int)t.size());
}  else {
t.erase(s[left++]);
}
}
return res;
}
};

``````

Java 解法三：

``````public class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0, left = 0, right = 0;
HashSet<Character> t = new HashSet<Character>();
while (right < s.length()) {
if (!t.contains(s.charAt(right))) {
res = Math.max(res, t.size());
} else {
t.remove(s.charAt(left++));
}
}
return res;
}
}
``````

### 代码2

``````/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const mapper = {}; // 记录已经出现过的charactor
let res = 0;
let slidingWindow = [];

for (let c of s) {
if (mapper[c]) {
// 已经出现过了
// 则删除
const delIndex = slidingWindow.findIndex(_c => _c === c);

for (let i = 0 ; i < delIndex; i++) {
mapper[slidingWindow[i]] = false;
}

slidingWindow = slidingWindow.slice(delIndex + 1).concat(c);
} else {
// 新字符
if (slidingWindow.push(c) > res) {
res = slidingWindow.length;
}
}
mapper[c] = true;
}
return res;
};
``````

评论
0 评论