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

LeetCode-day3

（参考了官网解法）

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

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

解题思路及实现：
1.暴力法

public static int lengthOfLongestSubstring(String s) {
		if(s.length()<=1) {
			return s.length();
		}
		int answer=0;
		int temp=0;
		HashMap<String, Integer> map=new HashMap<String, Integer>();
		for(int j=0;j<s.length();j++) {
			for(int i=j;i<s.length();i++) {
				if(!map.containsKey(s.charAt(i)+"")) {
					map.put(s.charAt(i)+"", i);
					temp++;
				
				}else {
			
					break;
				}
			}
			if(answer<temp) {
				answer=temp;
			}
			temp=0;
			map.clear();		
		}
	return answer;}

2.滑动窗口（sliding windown）

public static int lengthOfLongestSubstring2(String s) {
		int l=0;//左节点
		int r=0;//右节点
		HashSet<Character> set=new HashSet<Character>();
		int answer=0;
		while(r<s.length()) {
			if(!set.contains(s.charAt(r))) {//如果set中不包含r节点的字符
				set.add(s.charAt(r++));//就将该字符加入到set，并且右节点继续像右移一位
				answer=Math.max(answer, r-l);//比较字符串的长度
			}else {
				set.remove(s.charAt(l++));//如果包含了，就将set中的左节点的字符开始删除，直到又不包含右节点的字符
			}
		}
		return answer;
	}

3.优化滑动窗口
直接找到重复的那个字符的位置，将左节点直接挪到重复字符的下一个位置上

public static int lengthOfLongestSubstring3(String s) {
		HashMap<Character, Integer> map=new HashMap<Character, Integer>();
		int answer=0;
		for(int l=0,r=0;r<s.length();r++) {
			if(map.containsKey(s.charAt(r))) {
				l=Math.max(map.get(s.charAt(r)), l);
			}
			map.put(s.charAt(r), r+1);
			answer=Math.max(answer, r-l+1);
		}
		return answer;
	}