实用指南：LeetCode:无重复字符的最长子串

目录

解题过程:

描述:

分析条件:

正确解题思路:

通过这道题可以学到什么:

---

解题过程:

描述:

3. 无重复字符的最长子串

提示

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。

示例 1:

"abc"

示例 2:

"b"

示例 3:

"wke"

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

分析条件:

1.我们只需要最长数组的长度即可,因此我们实际上是要把可能得情况全部求出来并取其中的最大值,因此滑动数组是最优解

2.什么事滑动数组呢,尾指针遍历数组,头指针动态变化(根据是否有重复元素)

3.那么头指针如何动态变化呢,我们可以用一个HashMap集合记录每个元素上一次出现的位置,我们遇到重复元素,让头指针指向该重复元素在Map中记录的索引的下一个位置

正确解题思路:

class Solution {
public int lengthOfLongestSubstring(String s) {
//定义一个变量记录结果
int ans = 0;
int len = s.length();
//定义一个哈希数组记录当前字符索引
Map map = new HashMap<>();
for(int start = 0,end = 0; end < len;end++){
if(map.containsKey(s.charAt(end))){
//防止start回退
start = Math.max(start,map.get(s.charAt(end)) + 1);
}
//把当前元素的索引存入map集合
map.put(s.charAt(end),end);
ans = Math.max(ans,end - start + 1);
}
return ans;
}
}

通过这道题可以学到什么:

要注意取start和重复元素索引位置下一位中的最大值,防止start头指针回退