題目描述
Given a string, find the length of the longest substring without repeating characters.
給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度式撼。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"菠剩，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"桶至，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"匾旭，所以其長度為 3镣屹。
請注意，你的答案必須是 **子串** 的長度价涝，"pwke" 是一個子序列女蜈，不是子串。
我的垃圾思路
One
- 剛開始想耍一些"小聰明"色瘩，看有沒有巧妙的方法解決伪窖，當(dāng)時用了類似于Node的前后'指針'的方式發(fā)現(xiàn)有些用例是過不了的
- 后面用到了類似"滑窗"的方法，碰到重復(fù)字符則將滑窗寬度歸零居兆，且位置回到被重復(fù)字符的下一位置覆山。
- 但會出現(xiàn)死循環(huán)，因為沒把之前被重復(fù)的字符
remove掉 -- 后面發(fā)現(xiàn)只remove掉那個重復(fù)的字符的話史辙，有些沒有重復(fù)的字符在回退之后再次計算的時候汹买，會發(fā)生混亂<font color=grey size=2>(回退后再次走到之前不重復(fù)的字符時候佩伤，因為hash表中已經(jīng)在第一次put過了，所以這次一定會發(fā)生重復(fù)情況)</font> - 所以上面把滑窗歸零的時候是真正的歸零晦毙，包括存數(shù)據(jù)的hash表
上面方法應(yīng)該是
,因為會發(fā)生例如
abcdea在最后a發(fā)生重復(fù)生巡，就會完全回退到b位置---so low ；提交記錄耗時大概80+ms
Two
- 第二個方法是也兩個指針類似滑窗见妒， k指針一直前進(jìn)孤荣，發(fā)生重復(fù)時j指針移動到被重復(fù)字符的下一位置，但是只能往右移動须揣，不能回退
- 將
map<Character,Integer>中存放的之前被重復(fù)字符的value(即字符所在的索引)換為當(dāng)前發(fā)生重復(fù)的字符位置 -- 不是被重復(fù)字符 - 循環(huán)中一直保持
max最大 - 當(dāng)有其中一個指針到達(dá)終點(diǎn)時盐股，就可以退出了 ；由于
j,k代表的都是索引耻卡，所以最后結(jié)果 為max+1
Three
- 第二種方法發(fā)現(xiàn) k一直在++疯汁，其實(shí)就相當(dāng)于for循環(huán)的 i++，所以就換成for循環(huán)了 -- 復(fù)雜度應(yīng)該是
Two和Three 提交的耗時6ms,占用內(nèi)存35M--占用內(nèi)存竟然超過了 100%的java用戶ヽ(°° )ノ
leetcode-3-占用資源.jpg
源.jpg)
我的垃圾代碼
package com.dasnnj.practice.medium;
import java.util.HashMap;
import java.util.Map;
/**
* Description <p> TODO:
* 給定一個字符串卵酪，請你找出其中不含有重復(fù)字符的 最長子串 的長度幌蚊。
* <p>
* 示例 1:
* <p>
* 輸入: "abcabcbb"
* 輸出: 3
* 解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3溃卡。
* 示例 2:
* <p>
* 輸入: "bbbbb"
* 輸出: 1
* 解釋: 因為無重復(fù)字符的最長子串是 "b"溢豆，所以其長度為 1。
* 示例 3:
* <p>
* 輸入: "pwwkew"
* 輸出: 3
* 解釋: 因為無重復(fù)字符的最長子串是 "wke"瘸羡，所以其長度為 3漩仙。
* 請注意，你的答案必須是 子串 的長度犹赖，"pwke" 是一個子序列队他，不是子串。</p>
*
* @author DASNNJ <a href="mailto:dasnnj@outlook.com.com"> dasnnj@outlook.com </a>
* @date 2019-05-08 13:17
*/
public class LongestSubstringWithoutRepeatingCharacters {
public static void main(String[] args) {
LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters();
System.out.println(l.lengthOfLongestSubstring(""));
}
public int lengthOfLongestSubstring(String s) {
//One
/*char[] chars = s.toCharArray();
Map<Character, Integer> map = new HashMap<>(8);
//計算非重復(fù)字符的長度
Integer len = 0;
int max = 0;
//索引
Integer index;
for (int i = 0; i < chars.length; i++) {
//如果是正常進(jìn)行
//如果重復(fù)
if ((index = map.get(chars[i])) != null) {
//回退到重復(fù)的位置冷尉，從重復(fù)位置的下一位重新算漱挎，相當(dāng)于舍棄兩個重復(fù)字符中的第一個
i = index;
//長度歸零
len = 0;
//將map清空，從重復(fù)位置的下一位置重新計算 -- 清空是因為第一個重復(fù)的在上面提到是相當(dāng)于舍棄，不清空的話會影響下次循環(huán)的判斷
map.clear();
} else {
//沒重復(fù)當(dāng)然正常put 正常++
map.put(chars[i], i);
len++;
}
//每次循環(huán)都保持max最大
if (len > max) {
max = len;
}
}
return max;*/
if ("".equals(s)) {
return 0;
}
char[] chars = s.toCharArray();
//j k,用于Two方法的兩個指針---后面發(fā)現(xiàn)直接用for循環(huán)即可
int j = 0, k = 0, max = 0;
Integer ele;
Map<Character, Integer> sets = new HashMap<>(16);
//Three
for (int m = 0; m < chars.length; m++) {
//如果發(fā)生重復(fù)
if ((ele = sets.get(chars[m])) != null) {
// j指針指向兩個重復(fù)字符中的第一個的下一位置瞧预，j指針不能后退腻菇，只能前進(jìn)，所以下面有個判斷
if (j < ele + 1) {
j = ele + 1;
}
}
//不重復(fù)則是正常put白对，重復(fù)情況1.將j指針指向原字符的下一位2.用新字符替換掉map中原字符（主要是為了替換map中key為此字符 的value值也就是索引）
sets.put(chars[m], m);
//每次循環(huán)保持max最大
if (max < m - j) {
max = m - j;
}
}
//Two 原理同Three
/*while (j < chars.length && k < chars.length) {
if ((ele = sets.get(chars[k])) != null) {
if (j < ele + 1) {
j = ele + 1;
}
}
sets.put(chars[k], k);
k++;
if (max < k - j) {
max = k - j;
}
}*/
return max + 1;
}
}
