LeetCode——无重复字符的最长子串

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

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

示例2:

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

示例3:

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

解题思路

这里讲述的我自己的解题思路的确是笨的要死，不过也是我自己通过对问题的本质分析总结出来的，暂且记录一下，在有了自己的解题思路后去学习别人更加优秀的解题思想，对于我的提升还是蛮大的。

请看图:

首先对图中的变量做一下介绍：

char curchar; // 记录当前读取到的字符
String curMaxStr; // 记录最近最长无重复字符串
int curMaxLen; // 记录最近最长无重复字符串的长度
String totalMaxStr; // 记录总体最长无重复字符串
int totalMaxLen; // 记录总体最长无重复字符串的长度
复制代码

接下来是我对问题的思考：

1. 对字符串进行for循环遍历，使用 curChar 记录当前读取到的字符；
2. 判断 curMaxStr 中有没有这个字符 curChar ，如果没有，就将这个字符拼接到 curMaxStr ，并且将 curMaxLen 加1，如果 curMaxLen 大于等于 totalMaxLen ，就将 curMaxStr 和 curMaxLen 赋值给 totalMaxStr 和 totalMaxLen 。
3. 如果 curMaxStr 有这个字符 curChar ，那么从当前位置向前反序遍历，必然能找到与之重复的那个字符的位置，将重复的字符之后到当前 curChar 位置的字符串赋值给 curMaxStr ，如果 curMaxLen 大于等于 totalMaxLen ，就将 curMaxStr 和 curMaxLen 赋值给 totalMaxStr 和 totalMaxLen 。

具体代码

public static int lengthOfLongestSubstring(String s) {
        // 当字符串s的长度为0时，那么就没有最长子串了
        char curChar;
        String curMaxStr = "", totalMaxStr = "";
        int curMaxLen = 0, totalMaxLen = 0;
		if(s.length() == 0) {
            totalMaxLen = 0;
        }
        for(int i = 0; i < s.length(); i++) {
            curChar = s.charAt(i);
            // 当前字符与当前最长字符串中的字符没有重复时
            if (!curMaxStr.contains(String.valueOf(curChar))) {
            	// 将当前字符拼接到当前最长字符串上
				curMaxStr += curChar;
				// 当前最长长度+1
				curMaxLen ++;
				if (curMaxLen >= totalMaxLen) {
					totalMaxStr = curMaxStr;
					totalMaxLen = curMaxLen;
				}
				//System.out.println("++++curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
			}
            else {
            	// 记录重复点的位置
				int repeatPos = i;
				curMaxStr = String.valueOf(curChar);
				curMaxLen = 1;
				// i没有遍历到开始处，并且从重复位置向前移动的这个字符与重复字符不重复
				while(i > 0 && s.charAt(i - 1) != curChar) {
					curMaxStr = s.charAt(--i) + curMaxStr;
					curMaxLen++;
					//System.out.println("----curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
					if (curMaxLen >= totalMaxLen) {
						totalMaxStr = curMaxStr;
						totalMaxLen = curMaxLen;
					}
				}
				i = repeatPos;
			}
        }
        return totalMaxLen;
    }
复制代码

下面是我在结了这个问题之后，在评论区看到的别人的解法，感觉特别棒，在这里也分享处理，如果读者觉得我的想法太笨，可以看看这段代码：

public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        String str = "";
        for (int i = 0; i < s.length(); i++) {
			int index = str.indexOf(s.charAt(i));
			str = str + s.charAt(i);
			//出现重复
			if(index >= 0) {
				str = str.substring(index + 1);
			} else {
				if (str.length() > maxLength) {
					maxLength = str.length();
				}
			}
		}

        return maxLength;

    }
复制代码