算法——无重复字符的最长子串（思路+实现）

题目如下：

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

思路：题目要求的是最长不重复子串的长度。首先要遍历这个字符串，在遍历过程中得判断重复或者不重复，因此有遍历的过程中有两种情况：1.存在重复字符。2.不存在重复字符。

首先说不存在重复字符的情况：不存在重复字符只需要一直遍历直到结束，然后和已知最长不重复子串的长度进行比较，若大于已知最长不重复子串，则返回此长度。

若存在重复字符，则需要重新标记当前最长不重复子串的起始下标，那么重新标记到哪里？ 由于从上一个起始下标到当前重复的位置是之前判断过没有重复字符的地方，因此可以将重复字符的上一个位置的下标作为新一轮最长不重复子串的起始下标，但是这里有一个陷阱：当字符串是“abba”，当遍历到第二个a时，如果要回退到上一个a位置的下标，那么其实这时已经错了，因为这之间是存在“bb”这两个重复字符的，因此何时需要回退？应该是当上一个重复字符的位置下标大于当前start下标时，才会更新start为上一个重复字符的下标，这样可以避免重新选取起始下标是之间存在重复字符导致答案错误。因此可以使用HashMap、数组...来记录每个字符所对应的上一个位置的下标。需要注意的是每次遍历无论当前字符是否存在，都应该将当前字符的下标位置进行更新，以保证每次得到的下标位置都是上一个该字符的位置下标。

以下是代码实现：

public class pro10_14_11 {

    public static int lengthOfLongestSubstring(String s) {
        //处理为空情况
        if(s==null || s.equals(""))
            return 0;
        //存储每个字符的下标位置
        HashMap<Character,Integer> map=new HashMap<>();
        //count:最长不重复字符串的长度，start当前最长不重复字符串的起始地址，tmp:当前最长不重复字符串的长度
        int count=1,start=0,tmp=0;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.containsKey(ch)){
                //判断当前字符的上一个位置是否大于start的当前位置，只有大于才进行start的更新
                if(start<map.get(ch)){
                    start=map.get(ch);
                }
                //更新最长不重复子串的长度
                if(tmp>count){
                    count=tmp;
                }
                //出现重复字符后，更新的当前最长不重复子串的长度
                tmp=i-start;
            } else {
                //若当前字符重复，则当前最长不重复子串递增
                tmp++;
            }
            //每次都需要更新当前字符的下标位置
            map.put(ch,i);
        }
        //会有整个字符串（或者后面一部分不重复）的情况，对这个情况进行处理
        if(tmp>count){
            count=tmp;
        }
        //返回最终结果
        return count;
    }

    public static void main(String[] args) {
        String str="abba";
        System.out.println(lengthOfLongestSubstring(str));
    }
}