从零打卡leetcode之day 4--无重复最长字符串
前言
深知自己在算法方面上很菜，于是打算通过打卡的方式，逼自己一把。每天在leetcode上打卡，并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路，那么，别犹豫了，上车吧，一起学习一起探讨。
说明：有点抱歉，昨晚发的记得有写题目描述，但不知为啥，题目描述丢失了，可能是自己突然不小心删除了。
题目描述：
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
解题过程:
方法一：暴力版本
显然，对于这道题我们可以像以往一样，遍历所有子串，对于这个方法，我相信大家都能想到，我就直接贴代码了。如下
//三个for暴力解决
public static int lengthOfLongestSubstring(String s) {
int max = 0;
int temp = 0;
char[] arr = new char[s.length()];
for(int i = 0; i < s.length(); i++){
arr[i] = s.charAt(i);
temp = 1;
for(int j = i + 1; j < s.length(); j++){
int flag = 0;//用来判断s[j]是否在arr中
for(int k = i; k < i + temp; k++){
if(arr[k] == s.charAt(j)){
flag = 1;
break;
}
}
if(flag == 1){ break;//重复
} else {
arr[i+temp] = s.charAt(j);
temp++;
}
}
if(temp > max){
max = temp;
}
}
return max;
}前面两个for循环用来遍历所有子串，第三个for循环用来判断字符s.charAt(j)是否在子串中。
方法二：各种优化
优化策略1：大家想一个问题，对于第三个循环，我们在数组里查找该数组是否拥有某个字符，这个查找的过程的时间复杂度是O(n),我们是否有其他什么方法把查找的过程的复杂度降低到O(1)？
前几次我们都有用过hashMap来进行映射，实际上这里一样可以用hashMap来保存子串，然后再判断s.charAt(j)是否子串中，这样我们就可以把查找过程的复杂度降低到O(1)了。
优化策略2：假如给你一个字符串：
"abcdca"
我们在遍历子串的过程中，最开始我们从第一个元素'a'开始遍历，当我们遍历到'abcd'时，在继续查找的时候遇到'c'，此时"abcd"里面已经有'c'了，此时该子串查找完毕。此时长度为4，继续下一个子串的查找。
注意：我们继续下一个子串查找的时候，是从第二个元素'b'开始的。可是大家想一个问题，真的有必要从第二个元素'b'开始查找吗？，假如我们从'b'开始的时候，遍历到"bcd",继续遍历时又会再次遇到'c'，此时长度为3。比上一个子串4的长度小。
实际上，我们是没有必要从第二个元素开始查找的。我们直接从'd'开始查找就可以了，也就是说，如果 s[j]s[j] 在 [i, j)[i,j) 范围内有与 j'j′ 重复的字符。我们再下一次寻找子串时，直接从j'+1的位置开始就行了。如果你不是很理解为啥会这样的话，可以找一些元素模拟一下勒。
优化策略3：我们每次在寻找子串的时候，会把子串放进hashMap里，假如我们要寻找下一个子串的话，理论上是需要把hashMap里面的元素给清空，然后再用来放置新的子串的。
但实际上，是不需要这样子的，hashMap里面的元素是可以重复利用的。先上代码吧，然后我在画图解释下优化策略三。如下：
//用hashMap映射
public static int lengthOfLongestSubstring2(String s) {
int max = 0;//保存最长子串的长度
//用来记录子串是从哪个下标开始的
int i = 0;
Map<Character, Integer> map = new HashMap<>();
for(int j = 0; j < s.length(); j++){
if(map.containsKey(s.charAt(j))){
//从第一个重复元素的后一个开始
i = Math.max(map.get(s.charAt(j))+ 1, i);
}
//j - i + 1 表示计算此时子串的长度
max = Math.max(max, j - i + 1);
map.put(s.charAt(j), j);
}
return max;
}假设字符串为"abcba"，下面演示hashMap中元素的变化情况。
当j = 2。
当j = 3是，此时出现重复的字符(黄色的表示已经被代替的字符)。
当j = 4时。
j = 4时，hashMap有重复的字符a(下标为0的那个)，为啥不会把i定位到下标为2的元素上？(因为它都已经遍历到从下标我为3的那里了，怎么可能还会倒回去)
这种方法的时间复杂度为O(n)。
完
往期回顾：
假如你有更好的做法，欢迎提出来让大家涨涨知识哦。由于该公众号没有留言功能，为了大家更好的交流，我创建了一个微信群，大家可以在这里谈论有关算法的问题。不过该群是禁止发推文的。需要进群的伙伴可以加我为好友，备注“从0打卡leetcode”，我拉你进群。在公众号右下方有我的微信二维码。