代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
"abc",所以其
示例 2:
"b"
示例 3:
"wke"
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成方法一:双指针 + 哈希表
定义一个哈希表记录当前窗口内出现的字符,记 $i$ 和 $j$ 分别表示不重复子串的开始位置和结束位置,无重复字符子串的最大长度记为 ans
。
遍历字符串 s
的每个字符 $s[j]$,我们记为 $c$。若 $s[i..j-1]$ 窗口内存在 $c$,则 $i$ 循环向右移动,更新哈希表,直至 $s[i..j-1]$ 窗口不存在 c
,循环结束。将 c
加入哈希表中,此时 $s[i..j]$ 窗口内不含重复元素,更新 ans
的最大值。
最后返回 ans
即可。
时间复杂度 $O(n)$,其中 $n$ 表示字符串 s
的长度。
双指针算法模板:
for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(j, i)) {
++j;
}
// 具体问题的逻辑
}
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ss = set()
i = ans = 0
for j, c in enumerate(s):
while c in ss:
ss.remove(s[i])
i += 1
ss.add(c)
ans = max(ans, j - i + 1)
return ans
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> ss = new HashSet<>();
int i = 0, ans = 0;
for (int j = 0; j < s.length(); ++j) {
char c = s.charAt(j);
while (ss.contains(c)) {
ss.remove(s.charAt(i++));
}
ss.add(c);
ans = Math.max(ans, j - i + 1);
}
return ans;
}
}
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> ss;
int i = 0, ans = 0;
for (int j = 0; j < s.size(); ++j) {
while (ss.count(s[j])) ss.erase(s[i++]);
ss.insert(s[j]);
ans = max(ans, j - i + 1);
}
return ans;
}
};
func lengthOfLongestSubstring(s string) int {
ss := map[byte]bool{}
i, ans := 0, 0
for j := 0; j < len(s); j++ {
for ss[s[j]] {
ss[s[i]] = false
i++
}
ss[s[j]] = true
ans = max(ans, j-i+1)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
const ss = new Set();
let i = 0;
let ans = 0;
for (let j = 0; j < s.length; ++j) {
while (ss.has(s[j])) {
ss.delete(s[i++]);
}
ss.add(s[j]);
ans = Math.max(ans, j - i + 1);
}
return ans;
};
public class Solution {
public int LengthOfLongestSubstring(string s) {
var ss = new HashSet<char>();
int i = 0, ans = 0;
for (int j = 0; j < s.Length; ++j)
{
while (ss.Contains(s[j]))
{
ss.Remove(s[i++]);
}
ss.Add(s[j]);
ans = Math.Max(ans, j - i + 1);
}
return ans;
}
}
function lengthOfLongestSubstring(s: string): number {
const ss = new Set();
let i = 0;
let ans = 0;
for (let j = 0; j < s.length; ++j) {
while (ss.has(s[j])) {
ss.delete(s[i++]);
}
ss.add(s[j]);
ans = Math.max(ans, j - i + 1);
}
return ans;
}
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
var map = [Character: Int]()
var currentStartingIndex = 0
var i = 0
var maxLength = 0
for char in s {
if map[char] != nil {
if map[char]! >= currentStartingIndex {
maxLength = max(maxLength, i - currentStartingIndex)
currentStartingIndex = map[char]! + 1
}
}
map[char] = i
i += 1
}
return max(maxLength, i - currentStartingIndex)
}
}
proc lengthOfLongestSubstring(s: string): int =
var
i = 0
j = 0
res = 0
literals: set[char] = {}
while i < s.len:
while s[i] in literals:
if s[j] in literals:
excl(literals, s[j])
j += 1
literals.incl(s[i]) # Uniform Function Call Syntax f(x) = x.f
res = max(res, i - j + 1)
i += 1
result = res # result has the default return value
use std::collections::HashSet;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let s = s.as_bytes();
let mut set = HashSet::new();
let mut i = 0;
s.iter()
.map(|c| {
while set.contains(&c) {
set.remove(&s[i]);
i += 1;
}
set.insert(c);
set.len()
})
.max()
.unwrap_or(0) as i32
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。