This action will force synchronization from doocs/leetcode, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
"abc",所以其
示例 2:
"b"
示例 3:
"wke"
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成方法一:双指针 + 哈希表
定义一个哈希表记录当前窗口内出现的字符,i、j 分别表示不重复子串的开始位置和结束位置,ans 表示无重复字符子串的最大长度。
遍历 s 每个字符 c,若 [i, j - 1]
窗口内存在 c
,则 i 循环向右移动,更新哈希表,直至 [i, j - 1]
窗口不存在 c
,循环结束。将 c
加入哈希表中,此时 [i, j]
窗口内不含重复元素,更新 ans 的最大值:ans = max(ans, j - i + 1)
。
最后返回 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:
i = ans = 0
chars = set()
for j, c in enumerate(s):
while c in chars:
chars.remove(s[i])
i += 1
chars.add(c)
ans = max(ans, j - i + 1)
return ans
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, ans = 0;
Set<Character> chars = new HashSet<>();
for (char c : s.toCharArray()) {
while (chars.contains(c)) {
chars.remove(s.charAt(i++));
}
chars.add(c);
ans = Math.max(ans, j - i + 1);
++j;
}
return ans;
}
}
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let i = 0,
j = 0,
ans = 0;
let chars = new Set();
for (let c of s) {
while (chars.has(c)) {
chars.delete(s[i++]);
}
chars.add(c);
ans = Math.max(ans, j - i + 1);
++j;
}
return ans;
};
function lengthOfLongestSubstring(s: string): number {
// 滑动窗口+哈希表
let left = -1;
let maxLen = 0;
let hashTable = new Map();
for (let right = 0; right < s.length; right++) {
let cur = s.charAt(right);
if (hashTable.has(cur)) {
left = Math.max(left, hashTable.get(cur));
}
hashTable.set(cur, right);
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
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)
}
}
func lengthOfLongestSubstring(s string) int {
window := make(map[byte]int)
n := len(s)
ans := 0
left, right := 0, 0
for right < n {
b := s[right]
right++
window[b]++
for window[b] > 1 {
window[s[left]]--
left++
}
ans = max(ans, right-left)
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0, ans = 0;
unordered_set<char> chars;
for (char& c : s)
{
while (chars.count(c)) chars.erase(s[i++]);
chars.insert(c);
ans = max(ans, j - i + 1);
++j;
}
return ans;
}
};
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
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。