Longest Substring Without Repeating Characters (最长无重复字符的子串)

 

     思路：

     比如 ： "dvdfzxd"字符串，我要求他的最长无重复字符的子串。

     可以知道的，一定要从开头遍历到结尾。

     这样，从第一个开始，一直读，直到最后一个，如果读到的字符与之前的重复了，

     那么前面部分就可以看成一个符合要求的子串，记录它的长度。那么接下来就是跳过

     刚重复的字符，以它的下一个节点为起点，重新计算一个新的子串的长度。

     比如这里，遍历到第3个元素d时，与第一个d重复，那么记录，子串长度2，从v开始

     就算新的子串的长度。

     

 

    思路是这样，但是怎么知道之前的字符重复过了？

    HashMap能够很好的帮我们解决。

    用它来存储<字符，小标> 。

 

    但是，"abba"这种情况，该怎么解决了？

   当我们读到第2个a是，明显他们之间还有其他的重复字符。

   可以通过设置一个起点变量，来表示现在计算的子串的起点，同时如果重复，则每次都更新为

    最新的小标。

 

    综上，得到代码：

   

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character , Integer> map = new HashMap<> ();
        int sum = 0;
        int max = 0;
        int start = 0;
        for(int i = 0 ; i < s.length() ; i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)) {
                int idx = map.get(c);
                //如果重复的元素在新子串内
                if(idx >= start) {
                    //更新为最新的下标
                    map.put(c,i);
                    //最新的无重复元素的子串则是去掉第一个相同的元素
                    sum = i - idx;
                    //新子串的起点
                    start = idx + 1;
                } else {
                    //更新节点为最新的位置
                    map.put(c ,i);
                    sum++;
                } 
            } else {
                map.put(c , i);
                sum++;
            }
            max = Math.max(sum , max);
        }
        return max;
    }
}