无重复字符的最长字串

给定一个字符串 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);
    }
}