LeetCode--最长不含重复字符的子字符串
博客说明
文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！
说明
leetcode题，面试48
题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Go语言
思路
遍历字符串，使用map记录重复元素出现的位置，对比子串的长度，发现最长的及时更新
代码
func lengthOfLongestSubstring(s string) int {
//创建一个map集合
lastOccured := make(map[byte]int)
//计数器
startI := 0
//长度
maxLength := 0
//遍历string
for i, ch := range []byte(s) {
//判断集合不为空
if lastI, ok := lastOccured[ch]; ok && lastI >= startI {
startI = lastI + 1
}
//计算最长的子串
if i-startI+1 > maxLength {
maxLength = i - startI + 1
}
//记录最后一次出现的位置
lastOccured[ch] = i
}
return maxLength
}
Python语言
思路一（滑动窗口）
初始化头尾指针 head，tail；
-
tail 指针右移，判断 tail 指向的元素是否在 [head:tail] 的窗口内；
如果窗口中没有该元素，则将该元素加入窗口，同时更新窗口长度最大值，tail 指针继续右移；
如果窗口中存在该元素，则将 head 指针右移，直到窗口中不包含该元素。
返回窗口长度的最大值。
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
head = 0
tail = 0
# 判断是否为边界
if len(s) < 2:
return len(s)
# 两个指针停留在第一个元素的位置，初始长度为1
res = 1
while tail < len(s) - 1:
tail += 1
if s[tail] not in s[head:tail]:
res = max(tail-head + 1,res)
else:
while s[tail] in s[head:tail]:
head += 1
return res
思路二（哈希表）
-
tail指针向末尾方向移动； - 如果尾指针指向的元素存在于哈希表中：
-
head指针跳跃到重复字符的左边一位；
-
- 更新哈希表和窗口长度。
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
hashmap = {}
head,res = 0,0
for tail in range(n):
# 如果说尾指针存在哈希表中，把头指针跳转到开始重复元素的上一位
if s[tail] in hashmap:
head = max(hashmap[s[tail]],head)
# 更新哈希表
hashmap[s[tail]] = tail +1
# 更新长度
res = max(res,tail-head+1)
return res
C++
-
r指针向末尾方向移动； - 如果尾指针指向的元素存在于哈希表中：
-
l指针跳跃到重复字符的左边一位；
-
- 更新哈希表和窗口长度（时刻返回最大的值）。
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char,int> m;
int ret = 0,l = 0, r=0;
while(r<s.size()){
//判断边界
if(m.find(s[r]) != m.end()){
l = max(l,m[s[r]]+1);
}
m[s[r++]] = r;
ret = max(r-l,ret);
}
return ret;
}
};
C语言
思路
滑动窗口
代码
int lengthOfLongestSubstring(char* s){
int count[95]; // ASCII中存在95个可打印的字符，记录遍历s时遇到的字符
memset(count, 0, 95 * sizeof(int)); // 将count的值全部置为0
int max_lenght = 0; // 不含重复字符的子字符串的最大长度
int temp = 0; // 存储遍历s时所寻找到的不含重复字符的子字符串的长度
int p1 = 0, p2 = 0;
while(s[p1] != '\0' && s[p2] != '\0'){
if(count[s[p2] - ' '] == 0){ // 没有遇到重复字符
count[s[p2] - ' '] = 1; // 记录遇到的字符
p2 += 1;
temp = p2 - p1;
}
else{ // 遇到重复字符
temp = p2 - p1;
count[s[p1] - ' '] = 0; // 删除对p1位置字符的记录
p1 += 1; // p1右移
}
if(temp > max_lenght){
max_lenght = temp;
}
}
return max_lenght;
}
感谢
leetcode
以及勤劳的自己
