3. 无重复字符的最长子串：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
样例 1：
输入:
s = "abcabcbb"
输出:
3
解释:
因为无重复字符的最长子串是 "abc"，所以其长度为 3。
样例 2：
输入:
s = "bbbbb"
输出:
1
解释:
因为无重复字符的最长子串是 "b"，所以其长度为 1。
样例 3：
输入:
s = "pwwkew"
输出:
3
解释:
因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
分析：
- 面对这道算法题目，二当家的陷入了沉思。
- 官方题解使用滑动窗口，尝试从每个字符开始找无重复的最长子串。
- 而我们这里换一种方式，是判断到每个字符为止的无重复的最长子串。因为存储了每个字符的最后出现下标，所以不需要内层循环来滑动窗口，可以直接定位出子串的开始位置。
题解：
rust
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
// 存每个字符最后的下标
let mut last = [-1; 128];
// 子串下标的前一位
let mut left = -1;
// 结果
let mut ans = 0;
for (i, c) in s.chars().enumerate() {
// 右移left
left = left.max(last[c as usize]);
// 修改字符最后下标
last[c as usize] = i as i32;
// 刷新结果
ans = ans.max((i as i32) - left);
}
ans
}
}go
func lengthOfLongestSubstring(s string) int {
// 存每个字符最后的下标
last := make([]int, 128)
for i := range last {
last[i] = -1
}
// 子串下标的前一位
left := -1
// 结果
ans := 0
for i, c := range s {
// 右移left
if last[c] > left {
left = last[c]
}
// 修改字符最后下标
last[c] = i
// 刷新结果
if i-left > ans {
ans = i - left
}
}
return ans
}c++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 存每个字符最后的下标
int last[128];
memset(last, -1, sizeof(int) * 128);
int left = -1;
int ans = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
// 右移left
left = max(left, last[c]);
// 修改字符最后下标
last[c] = i;
// 刷新结果
ans = max(ans, i - left);
}
return ans;
}
};c
int lengthOfLongestSubstring(char * s){
// 存每个字符最后的下标
int last[128];
memset(last, -1, sizeof(int) * 128);
int left = -1;
int ans = 0;
for (int i = 0; s[i] > 0; ++i) {
char c = s[i];
// 右移left
left = fmax(left, last[c]);
// 修改字符最后下标
last[c] = i;
// 刷新结果
ans = fmax(ans, i - left);
}
return ans;
}python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 存每个字符最后的下标
last = [-1] * 128
# 子串下标的前一位
left = -1
# 结果
ans = 0
for i in range(len(s)):
c = ord(s[i])
# 右移left
if last[c] > left:
left = last[c]
# 修改字符最后下标
last[c] = i
# 刷新结果
if i - left > ans:
ans = i - left
return ans
java
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
