题目描述

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

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

解题思路

这一个题目的解题思路是使用一种类似于贪心算法的思想，对题目进行求解。
具体的求解方法就是，从左往右遍历字符串，并且维持一个“滑动窗口”，这个窗口有以下三个特性：

• “滑动窗口”中没有重复的字符
• “滑动窗口”的最右元素表示以该元素作为结束符号的“无重复字符的最长子串”
• 从左往右遍历的过程中，“滑动窗口”出现的最大长度就是字符串的“无重复字符的最长子串”的长度

基于以上的特性，我们只需要在遍历的过程中，计算当前滑动窗口的长度，若大于目前记录的“无重复字符的最长子串”的长度，则更新max。

判断在当前无重复子串中是否存在该字符：使用一个索引left记录当前子串的最左边的字符位置，使用一个int数组，记录对应字符的最后一次出现的位置(索引就是字符对应的“ACSII码”)。判断一个字符是否在当前子串中，只需要拿该字符的ASCII码为下标，查询int数组，获取该字符最后一次出现的位置i，i若小于left，则表示该字符不在当前子串中。

简单示意图

• 字符无重复的情况：
  
• 字符重复的情况：
  
  

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {


        if(s.length() == 0)return 0;
        
        char[] M = s.toCharArray();     //将字符串转换为字符数组
        int[] A = new int[256];         //用来记录对应字符的最后一次出现的位置
        A[M[0]] = 1;                    //找到第一个字符的映射地址，填入它的最后一次出现的位置"1"(注意：从"1"开始算起)
        int left = 1;                   //记录当前子串的起始位置(注意：从"1"开始算起)
        int tmp = 1;                    //记录当前子串的长度
        int max = 1;                    //记录最长无重复字符的长度


        for(int i = 1; i < M.length; i++){
            if(A[M[i]] < left){          //在当前滑动窗口没有重复
                max = Math.max(max, ++tmp);
            }
            else{                       //在当前滑动窗口重复
                left = A[M[i]];
                tmp = i - left + 1;
            }
            A[M[i]] = i + 1;            //更新当前遍历到的字符的“最后一次出现的位置”(注意：从"1"开始算起，所以需要“+1”)
        }
        return max;
    }
}