【JAVA】每天两道算法题0910_双指针，滑动窗口。

深碍√TFBOYSˉ_ 2021-09-24 16:08 277阅读 0赞

### 这里写自定义目录标题 ###

*  题目来源：LeetCode

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

> 示例 1:  
> 输入: “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。  
> 示例 2:  
> 输入: “bbbbb”  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。  
> 示例 3:  
> 输入: “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

*  解题思路：  
    1.双指针，start指针记录子串的开始，end指针记录子串的结尾。  
    2.end指针遍历整个字符串，将字符串和下标放在HashMap中。在遍历过程中记录并更新 子串的长度。  
    3.end指针遍历的时候，如果end指针指向的地址的值在HashMap中已经存过了，则改变start的值，使得start指向和end指针指向的字符相同的字符的下一位。记录并更新子串的长度。
 *  代码实现：

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            HashMap<Character, Integer> map = new HashMap<>();
            int maxLen = 0;
            int n = s.length();
            for (int start = 0, end = 0; end < n; end++) { 
                if (map.containsKey(s.charAt(end))) { 
                    start = Math.max(start, map.get(s.charAt(end)) + 1);
                }
                map.put(s.charAt(end), end);
                maxLen = Math.max(maxLen, end - start +1);
            }
            return maxLen;
        }
    }