LeetCode 第三题
无重复字符的最长子串
难度中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “”
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
重点：
需要记录两个位置.字串的左边的下标,以及右边的下标
做法：
可以循环，可以用[map,vector]只要可以记录字符位置的基本都可以实现
C++解法
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
static int lengthOfLongestSubstring(string s) {
//这边随便用什么。map什么的都可以主要要记录字符的下标
vector<int> m(128, 0); //ASCII码范围：0-127
int res = 0;
int left = 0; //记录下标 从0开始
for (int right = 0; right < s.size(); right++) {
char chr = s[right];
//证明这个字符出现过
if(m[chr]!=0) {
//对比最近这个字符出现的下标,是否在当前的字串当中。
//滑动窗口的精髓。左边的界限。往右移动一个，把之前出现的这个字符过滤掉。
left = max(left, m[chr]);
//为什么不能发现的时候在下标+1呢，
//答：因为发现的字符可能在窗口之外
}
//当前下标+1， 这个+1，是为了下次发现的同样字符的时候把之前那个下标往后移动一个。把这个同样的字符给过滤掉。
//这点很难理解
m[chr] = right+1;
//和以往子串最大长度对比。
res = max(res, right - left+1);
}
return res;
}
};
int main()
{
std::string str="aa";
std::cout<<Solution::lengthOfLongestSubstring(str)<<std::endl;
return 0;
}
C++ 翻译golang
func max(a, b int) int{
if a > b {
return a
}
return b
}
func lengthOfLongestSubstring(s string) int {
//这边的map 也可以用切片
//m := (make[]int32, 128); 这步没有测试过
m := make(map[int32]int)
res:=0
left:=0
for index, info := range s {
chr := info
if m[chr] != 0 {
left = max(left, m[chr])
}
m[chr] = index+1
res = max(res, index-left +1)
}
return res;
}
可以关注我一起刷题，一起进步。谢谢
