点击上方“蓝色字体”，选择“设为星标”
每天复习一道面试题，轻松拿大厂Offer~
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 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)
维护数组：
使用一个数组来维护滑动窗口，遍历字符串，判断字符是否在滑动窗口数组里
- 不在则
push 进数组 - 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符
push 进数组 - 然后将
max 更新为当前最长子串的长度 - 遍历完，返回
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 开始的最大的不重复的字符序列
复杂度分析
代码
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 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 } 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();
//
map mp;for(int i=0;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 occ;
int n = s.size();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;// 枚举左指针的位置，初始值隐性地表示为 -1for (int i = 0; i if (i != 0) {// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}while (rk + 1 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) 前面包含 后面不包含
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
while (end {
char tmpChar = s[end];
for (int index = start; 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 map = new HashMap<>();for(int i=0;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 map = new HashMap<>();for (int end = 0, start = 0; 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 int pos = s.indexOf(s.charAt(i),flag);
if (pos 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 题解 | 每日一题? 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。
-
完 -
关注公众号「
IT平头哥联盟
」，一起进步，一起成长！
002. 两数相加 | Leetcode题解
001. 两数之和 | Leetcode题解
转播
