剑指 Offer 48. 最长不含重复字符的子字符串
题意：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
解题思路
解法1：-DP+哈希
1.分析题意，我们定义，S[n]为字符最长的不包含重复字符的子字符串，我们知道这个目标字符串，不也就知道它的长度了吗
2.接下来思考一下，S[n]、S[n-1]有什么关系
3.推导规律可知，if S[n-1] 字符串中不含有s.charAt(n)，则S[n] = S[n-1] + s.charAt(n)
4.if S[n-1] 字符串中含有s.charAt(n)，则S[n] =S[n-1].subString(s.charAt(n)出现的位置) + s.charAt(n)
5.还有一个问题，如何判断S[n-1]所指的字符串中是否含有s.charAt(n)，我们首先想到的是利用set的不可重复性
6.如果set.add一直成功，证明没有重复，如果失败，则证明此时有重复
解法2：-滑动窗口+哈希
1.if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0
2.划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0
3.使用哈希表map统计各字符最后一次出现的索引位置
4.当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新
5.当index>start时，start更新为当前的index,否则保持不变
6.注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入
7.如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
8.i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新
解题遇到的问题
无
后续需要总结学习的知识点
hashset、hashmap内部为什么是无序的？需要从源码角度，总结分析
##解法1
import java.util.Iterator;
import java.util.LinkedHashSet;
class Solution {
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb"));
}
public static int lengthOfLongestSubstring(String s) {
// 分析题意，我们定义，S[n]为字符最长的不包含重复字符的子字符串，我们知道这个目标字符串，不也就知道它的长度了吗
// 接下来思考一下，S[n]、S[n-1]有什么关系
// 推导规律可知，if S[n-1] 字符串中不含有s.charAt(n)，则S[n] = S[n-1] + s.charAt(n)
// if S[n-1] 字符串中含有s.charAt(n)，则S[n] =
// S[n-1].subString(s.charAt(n)出现的位置) + s.charAt(n)
// 还有一个问题，如何判断S[n-1]所指的字符串中是否含有s.charAt(n)，我们首先想到的是利用set的不可重复性
// 如果set.add一直成功，证明没有重复，如果失败，则证明此时有重复
if (s.length() <= 1) {
return s.length();
}
int max = 0;
LinkedHashSet<Character> set = new LinkedHashSet<Character>();
for (int i = 0; i < s.length(); i++) {
if (!set.add(s.charAt(i))) {
// 如果add失败，则此时 S[n-1] 字符串中含有s.charAt(n)
Iterator<Character> iterator = set.iterator();
char c = iterator.next();
while (iterator.hasNext()) {
iterator.remove();
if (c == s.charAt(i)) {
break;
} else {
c = iterator.next();
}
}
set.add(s.charAt(i));
}
max = Math.max(max, set.size());
}
return max;
}
}
##解法2
import java.util.HashMap;
class Solution {
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb"));
}
public static int lengthOfLongestSubstring(String s) {
// if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
// 划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
int max = 0, start = -1;
// 使用哈希表map统计各字符最后一次出现的索引位置
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char tmp = s.charAt(i);
// 当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
// 当index>start时，start更新为当前的index,否则保持不变。
// 注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
if (map.containsKey(tmp))
start = Math.max(start, map.get(tmp));
// 如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
map.put(tmp, i);
// i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
max = Math.max(max, i - start);
}
return max;
}
}
