LeetCode:无重复字符的最长子串

目录

解题过程:

描述:

分析条件:

正确解题思路:

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

---

解题过程:

描述:

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 由英文字母、数字、符号和空格组成

分析条件:

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

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

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

正确解题思路:

class Solution {public int lengthOfLongestSubstring(String s) {//定义一个变量记录结果int ans = 0;int len = s.length();//定义一个哈希数组记录当前字符索引Map<Character,Integer> 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头指针回退