3. 无重复字符的最长子串
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路一：暴力解决法
最暴力的解决方法是这样的，遍历该字符串的所有子字符串，并去除掉所有包含重复字符的子字符串。这样的话找出的最长子串就是我们需要的答案。其中去除含有重复字符的子字符串的方法是利用hashSet逐步添加子字符串字符，若已存在则重复。
代码:
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int length = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (allUnique(s, i, j)) length = Math.max(ans, j - i);
return length;
}
public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>();
for (int i = start; i < end; i++) {
Character ch = s.charAt(i);
if (set.contains(ch)) return false;
set.add(ch);
}
return true;
很明显该方法时间复杂度为O（n^3），是肯定不能通过的。
思路二：hashset滑动窗口解法
思路是这样的，使用hashSet表示了一个[i j)左闭右开的滑动窗口，该滑窗表示当前子字符串。当该窗口j向右滑动时，先判断s.charAt(j)是否在HashSet中，若不在，将其放入滑窗里。如果在的话，需要将滑动窗口以存在的字符删除，并将新的字符放入。
注意，删除已存在字符的时候，该字符前面如果有字符的话也要删除。 例如hashSet中此时是{a,b,c}此时j向右滑动一位，s.charAt(j)为c，那么a会先被删除，接着是b，最后删除和s.charAt(j)相同的c，此时hashSet为空了。删除完成后，下一步就是将新的c放入hashSet。
int n = s.length();
Set<Character> set = new HashSet<>();
int length = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
length = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return length;
该方法的时间复杂度为O（2n）=O（n）。
思路三：HashMap优化滑动窗口
我们很容易发现，我们可以进一步优化hashSet滑动窗口的代码，如果我们将判断重复字符的方法从遍历HashSet集合，改为使用HashMap映射的话，我们找到重复的字符时，也不用像上面一个一个的删除，直接可以跳过这些字符。我们的O（2n）步骤就变为了O（n）。
int n = s.length();
int length= 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);
}
length = Math.max(length, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return length;
思路四：字符数组索引
既然我们可以想到使用HashMap映射来存放子字符串，那么在字符串问题中，字符索引数组就很容易想到了。
int n = s.length(), length = 0;
int[] index = new int[26];
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j) - 'a'], i);
length = Math.max(length, j - i + 1);
index[s.charAt(j) - 'a'] = j + 1;
}
return length;
以上就是这个问题的一些解法了，答案参考了Leetcode的官方解答，有兴趣的可以自己看下
点击这里查看
