Leetcode.3 无重复字符的最长子串——超过100%的解法

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

        示例1：

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

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

        代码如下： 

 public int lengthOfLongestSubstring(String s) {
        if(s == null || s.equals("")){
            return 0;
        }
        //以i结尾往左推多远不重复 （考虑a上次出现的位置以及i-1能推多远）
        char[] chars = s.toCharArray();
        int n = chars.length;
        //0-255的ASCII码  用256长度数组能表示所有字符 ASCii码一个字节 最长256 不过目前是定义了128个字符
        //map[i] = v 代表i这个ascii码上次出现在v位置
        //char字符放入map数组中会自动转化为int类型 其值就是char字符的ascii码值 比如'a'就是97
        int[] map = new int[128];
        for(int i = 0; i < map.length; i++){
            map[i] = -1;//代表所有字符都在-1位置出现过
        }
        int ans = 1;//初始答案
        int pre = 1;//上一个位置向左推了多长（包括自己）
        map[chars[0]] = 0;//第一个字符在
        for(int i = 1; i < n; i++){
            //考虑字符char[i]上一次出现的位置 
            //例如adcba 01234那么长度就是字符char[i]现在的位置i减去上一次位置map[char[i]]
            // 4 - 0 = 4 也就是dcba
            int p1 = i -map[chars[i]];
            //考虑前一个位置向左推了多少 加上自己 就是自己能推的位置
            int p2 = pre + 1;
            //取二者最小值就是现在位置能向前推的长度
            int cur = Math.min(p1,p2);
            //取所有答案的最大值
            ans = Math.max(ans,cur);
            //后面继续循环，所以更新pre 和char[i]上一次出现的位置
            pre = cur;
            map[chars[i]] = i;
        }
        return ans;
    }

         主要的思想还是动态规划，考虑的是以i结尾的字符能够往前推多远，这与前一个字符能往前推多远有关，用一个数组map存储该字符上次出现的位置，初始化为-1，是为了在计算距离时，计算式子统一。