leetcode3. Longest Substring Without Repeating Characters

解法一：

1.维护三个变量:

max用于记录当前最大值，
next表示当前维护的正确子串，
pre表示之前出现的重复字符再上一次出现的最靠前位置

A1:当前重复字符当前位置
A2:当前重复字符上一次位置

B1:A之前某个重复字符的位置
B2:A之前某个重复字符的上一次位置，其中有B2是所有A之前重复字符中，上一次出现位置最靠前这个特性

  程序一直运行，直到遇到一个出现过的字符，判断A2和B2做比较，如果A2比B2大，则说明A1和A2之间没有包围B1和B2之间的位置，则可以直接做减法操作来更新next。如果A2小于B2，则A1和A2之间包围了B1和B2之间的位置，不能直接减，因为该范围内有其他重复字符，只能让next加1。

代码实现如下:

    public static int lengthOfLongestSubstring(String s) {
        if(s.equals(""))
            return 0;

        int[] pos = new int[130];                          //记录某个字母最后出现的位置

        int max = 1;
        int next = 1;
        int pre = 0;

        int i = 1;
        pos[s.charAt(0)] = 1;                              //初始化
        for( ; i < s.length(); i++) {

            int now_pos = pos[s.charAt(i)];                //判断当前字母是否已经出现过

            if(now_pos == 0){                               //未出现过
                next++;                                     //长度加1
            }
            else {                                          //出现过
                if(now_pos < pre )                          //如果之间包含其他重复字符
                    next++;
                else {                                      //之间未包含其他重复字符
                    next = i + 1 - now_pos;
                    pre = now_pos;                          //记录上一次出现过相同字符的位置
                }
            }

            pos[s.charAt(i)] = i + 1;                       //更新出现的位置

            if(max < next)                                  //更新max
                max = next;
        }

        return max;
    }

解法二

  使用start和end两个指针进行搜索，start代表候选的最长子串的开头，end代表候选的最长子串的结尾。start不动，向后移动end，直到找到一个相同的字符，当前候选子串长度就是(end-start)，用来更新max。下一次搜索应该从该重复字符在start后第一次出现的位置的下一个位置开始。例如agbcebf，刚开始start为0，end也为0，向后搜索，end=5时发现b是重复字符，则下次start应该从第一个b的下一个位置开始，即下一次start=3。

代码实现如下:

    public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        int start = 0;                                   //子串开头
        int end = 0;                                     //子串结尾
        int n = s.length();
        int[] exist = new int[130];                      //记录字符是否出现过


        while(end < n) {
            //说明已经出现过，这就是本次查找最大子串
            if(exist[s.charAt(end)] > 0) {               //发现重复字符
                if(end - start  > max)
                    max = end - start;

                while(s.charAt(start) != s.charAt(end)) {
                    exist[s.charAt(start)] = 0;          //重置0
                    start++;
                }

                start++;                                 //start更新为重复字符下一位置
                end++;                                   //end也往后加1
            }
            else {
                exist[s.charAt(end)] = 1;

                end++;
            }
        }

        if(n - start > max)                               //补上最后一次判断
            max = n - start;

        return max;
    }