LeetCode_3 “无重复字符的最长字串”

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路
拿到这道题的第一想法就是暴力解法，枚举所有可能的子串情况，在其中找到最长的子串。我是结合HashMap来实现的，具体的思路就是：设置双重循环，外层以每一个字符为起点进行最长子串的寻找，内层遍历该起点之后的字符，若与之前没有重复的字符，则将该字符添加到HashMap中，最长子串的长度+1，若与之前有重复的字符，则清空HashMap，跳出内层循环，以下一个字符为起点进行寻找。代码如下所示：

public int lengthOfLongestSubstring(String s) {
		int length = 0;
		Map<String,Boolean> map = new HashMap<String,Boolean>();
		for(int i=0; i<s.length(); i++) {
			int tmp = 0;
			for(int j=i; j<s.length(); j++) {
				String str = s.substring(j,j+1);
				if(map.get(str) == null) {	// 哈希表中不存在该字符
					map.put(str, true);	
					tmp ++;
					if(tmp > length) {
						length = tmp;
					}
				} else {	// 存在重复字符
					map.clear();
					break;
				}
			}
		}
		return length;
    }

提交之后，代码通过了。但是效率并不高，进一步学习之后发现了更好更高效的方法：滑动窗口。由于小编也是第一次听说这个概念，进行初步的学习之后也算是有了一些了解。它是数组和字符串问题中常用的抽象概念，其本质就是在使用两个指针i和j卡在窗口的两边，然后使窗口沿着某一方向滑动，比如我们将窗口[i,j)向右滑动一个单位，窗口就变为[i+1,j+1)。结合我们这道题目来说，定义窗口[i,j)（最初i=j），然后不断滑动j寻找最长子串，如果遇到有重复的字符，就滑动i，确保窗口内永远是没有重复字符的。如下如所示：

代码如下：

public int method_3(String s) {
		int n = s.length(), ans = 0;
		Map<Character,Integer> map = new HashMap<>();
		for(int j=0, i=0; j<n; j++) {
			if(map.containsKey(s.charAt(j))){
				i = Math.max(map.get(s.charAt(j)), i);
			}
			ans = Math.max(ans, j-i+1);
			map.put(s.charAt(j), j+1);
		}
		return ans;
	}