题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
难度：
- 难度：中等
- 支持语言：JavaScript、Java、Python、C++
相关标签
相关企业
- 阿里
- 字节
- 腾讯
- 美团
思路
题目要求连续， 我们考虑使用滑动窗口。 而这道题就是窗口大小不固定的滑动窗口题目，然后让我们求满足条件的窗口大小的最大值，这是一种非常常见的滑动窗口题目。
算法：
用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
- 如果当前遍历到的字符从未出现过，那么直接扩大右边界；
-
如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
-
重复（1）（2），直到窗口内无重复元素；
-
维护一个全局最大窗口 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果;
-
最后返回 res 即可;
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
维护数组：
使用一个数组来维护滑动窗口，遍历字符串，判断字符是否在滑动窗口数组里
1. 不在则 push 进数组
2. 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
3. 然后将 max 更新为当前最长子串的长度
4. 遍历完，返回 max 即可
滑动窗口 暴力解法：
- 暴力解法时间复杂度较高，会达到 O(n^2)O(n 2)，故而采取滑动窗口的方法降低时间复杂度
- 定义一个
map数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复 - 我们定义不重复子串的开始位置为
start，结束位置为end - 随着
end不断遍历向后，会遇到与[start, end]区间内字符相同的情况，此时将字符作为key值，获取其value值，并更新start，此时[start, end]区间内不存在重复字符 - 无论是否更新
start，都会更新其 map 数据结构和结果ans。
关键点
- mapper 记录出现过并且没有被删除的字符
- 滑动窗口记录当前 index 开始的最大的不重复的字符序列
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
代码
JavaScript 实现
/**
* @作者：user7746o
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/zi-jie-leetcode3wu-zhong-fu-zi-fu-de-zui-chang-zi-/
*/
var lengthOfLongestSubstring = function(s) {
let arr = [], max = 0
for(let i = 0; i < s.length; i++) {
let index = arr.indexOf(s[i])
if(index !== -1) {
arr.splice(0, index+1);
}
arr.push(s.charAt(i))
max = Math.max(arr.length, max)
}
return max
};
/**
* @作者：Heternally
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javascriptjie-fa-chao-9998-by-heternally/
*/
var lengthOfLongestSubstring = function(s) {
let num = 0,res = 0;
let m = '';
for (n of s) {
if (m.indexOf(n) == -1) {
m += n;
num++;
res = res < num ? num: res;
} else {
m += n;
m = m.slice(m.indexOf(n)+1);
num = m.length;
}
}
return res;
};
C++ 实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0, start = 0;
int n = s.length();
/* 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
map<char, int> mp;
for(int i=0;i<n;i++)
{
char alpha = s[i];
if(mp.count(alpha))
{
start = max(start, mp[alpha]+1);
}
ans = max(ans, i-start+1);
// 字符位置
mp[alpha] = i;
}
return ans;
}
};
/**
* @作者：LeetCode-Solution
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
/**
* @作者：pinku-2
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
*/
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
//s[start,end) 前面包含 后面不包含
/* 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
while (end < sSize)
{
char tmpChar = s[end];
for (int index = start; index < end; index++)
{
if (tmpChar == s[index])
{
start = index + 1;
length = end - start;
break;
}
}
end++;
length++;
result = max(result, length);
}
return result;
}
};
Java 实现
- 思路：
- 暴力解法时间复杂度较高，会达到 O(n^2)O(n2 )，故而采取滑动窗口的方法降低时间复杂度
- 定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
- 我们定义不重复子串的开始位置为 start，结束位置为 end
- 随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
- 无论是否更新 start，都会更新其 map 数据结构和结果 ans。
- 时间复杂度：O(n)O(n)
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0, start = 0;
int n = s.length();
//
Map<Character, Integer> map = new HashMap<>();
for(int i=0;i<n;i++)
{
char alpha = s.charAt(i);
if(map.containsKey(alpha))
{
start = Math.max(start, map.get(alpha)+1);
}
ans = Math.max(ans, i-start+1);
// 字符位置
map.put(alpha, i);
}
return ans;
}
}
/**
* @作者：guanpengchn
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
*/
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int end = 0, start = 0; end < n; end++) {
char alpha = s.charAt(end);
if (map.containsKey(alpha)) {
start = Math.max(map.get(alpha), start);
}
ans = Math.max(ans, end - start + 1);
map.put(s.charAt(end), end + 1);
}
return ans;
}
}
/**
* @作者：VioletKiss
* @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/
*/
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int flag = 0;
int length = 0;
int result = 0;
while (i < s.length()) {
int pos = s.indexOf(s.charAt(i),flag);
if (pos < i) {
if (length > result) {
result = length;
}
if (result >= s.length() - pos - 1) {
return result;
}
length = i - pos - 1;
flag = pos + 1;
}
length++;
i++;
}
return length;
}
}
Python3 实现
from collections import defaultdict
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = 0
ans = 0
counter = defaultdict(lambda: 0)
for r in range(len(s)):
while counter.get(s[r], 0) != 0:
counter[s[l]] = counter.get(s[l], 0) - 1
l += 1
counter[s[r]] += 1
ans = max(ans, r - l + 1)
return ans
# @作者：powcai
# @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.add(s[i])
return max_len
# @作者：marcusxu
# @链接：链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/python3ti-jie-chao-jian-dan-de-dong-tai-gui-hua-ji/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if s == '':
return 0
if len(s) == 1:
return 1
def find_left(s, i):
tmp_str = s[i]
j = i - 1
while j >= 0 and s[j] not in tmp_str:
tmp_str += s[j]
j -= 1
return len(tmp_str)
length = 0
for i in range(0, len(s)):
length = max(length, find_left(s, i))
return length
其他
- 原题leetcode链接：3.longest-substring-without-repeating-characters
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。
更多题解可以访问我的 码农周刊 仓库：https://github.com/meibin08/free-programming-books， 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发，我想请你帮我两个小忙：
- 把这篇文章分享给你的朋友 / 交流群，让更多的人看到，一起进步，一起成长！
- 关注公众号 「画漫画的程序员」，公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有，如若转载，请注明出处
转载请注明：文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com
微信扫一扫 
admin 
