无重复字符的最长字串

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

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

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

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

提示：0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路：本题用到了滑动窗口的思想。采用两个指针，分别指向子串的左右端，然后检查不重复的字符。向右遍历字符，如果遍历到的新字符不存在于当前子串中，就把右指针向右滑动，如果有重复了，就从子串中找和他重复的那个字符，把左指针放到找到的这个字符的后面。

对于abcabcbb字符串来说，首先左指针指向a, 右指针也指向a。然后往后找，右指针指向b, 不重复，继续，右指针指向c, 不重复，继续。右指针指向a，发现重复了。此时子串是abca, 此时应该把左指针移到第一个a的后面，也就是b的位置，此时子串就不重复了，继续，右指针指向b，此时子串是bcab，又重复了，左指针应该指向c。然后再继续……

代码一：

package text11;

import java.util.HashMap;
public class Solution {
	public static int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
            	//containsKey() 方法检查 hashMap 中是否存在指定的 key 对应的映射关系。
            	//string.charAt方法返回指定索引处的char值。
                left = Math.max(left,map.get(s.charAt(i)) + 1);
                
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
        
    }

    public static void main(String args[]) {
    	String ss="abcabcbb";
    	int aa= lengthOfLongestSubstring(ss);
    	System.out.print(aa);
    }
}

代码二：

package text11;

public class Solution {	
	public static int lengthOfLongestSubstring1(String s) {
		 if (s.length() < 2) return s.length();
	     int flag=0;//子串起始位置
	     int max = 0;
	     int len = 0;

	     for (int i = 0; i < s.length(); i++) {
	        int index = s.indexOf(s.charAt(i),flag);
	        //s.indexOf从flag位置处开始检索s.charAt(i)字符，返回他的位置。
	        if(index < i){//从flag开始 出现了重复字符
	            if(max<len){//记录len
	                max = len;
	            }
	            flag = index+1;//记录子串起始位置
	            len = i-flag+1;//重新计算字串长度
	        }
	        else{
	            len++;
	        }
	    }
	    return len>max?len:max;//若最后一个子串没有出现重复字符就需要判断
	}
	
	

    public static void main(String args[]) {
    	String ss="abcabcbb";
    	int aa= lengthOfLongestSubstring1(ss);
    	System.out.print(aa);
    }
}