我的思路

原始代碼

我發現我雖然解決問題了，但是我的思路不簡潔，不明白。

這個題本質上還是滑動窗口的問題。

具體思路為

1. 先定義兩個指針，對應滑動窗口的兩個邊界

2. 關鍵是：定義一個集合，來判斷這個窗口中的元素是否存在重復，如果存在重復的話，就把第一個元素刪掉。left右移，縮小窗口

   1. 除了這個點之外，這個題沒什么難點

public int lengthOfLongestSubstring(String s) {int len = s.length();if(len<=1){return len;}int low=0,fast=1;int max = 0;List<Character> list = new ArrayList<>();list.add(s.charAt(0));for(;fast<len;fast++){if(list.contains(s.charAt(fast))){list.add(s.charAt(fast));//當前元素重復了，需要移動left左指針。while (true){if(low<fast&&list.get(0)==s.charAt(fast)) {list.remove(0);low++;break;}list.remove(0);low++;}}else {list.add(s.charAt(fast));}if(max<list.size()){max = list.size();}}return max;
}

簡化代碼

這個題目本身不難，我在想我怎么簡化代碼，我最初始的代碼之所以這么復雜是因為我沒有想到判斷元素是否存在和移除元素是可以放在一起的。只要list中還存在這個元素，那么就已知移除。而不是逐漸遍歷這個集合去不斷的尋找這個元素。

注意

如果想要更快的話，可以把這個list換成這個set

public int lengthOfLongestSubstring(String s) {int len = s.length();int max = 0,low=0;List<Character> list = new ArrayList<>();for(int fast=0;fast<len;fast++){char c = s.charAt(fast);while (list.contains(c)){list.remove(0);low++;}list.add(c);max = Math.max(max,fast-low+1);}return max;
}

靈神

靈神的思路我大致看了一下，大體流程和我的相似，區別在于，我是利用list集合進行判斷的，靈神使用一個長度為128的數組 進行判斷，因為字母ASCII碼可以當作這個數組的下標

思路一

class Solution {public int lengthOfLongestSubstring(String S) {char[] s = S.toCharArray(); // 轉換成 char[] 加快效率（忽略帶來的空間消耗）int n = s.length;int ans = 0;int left = 0;int[] cnt = new int[128]; // 也可以用 HashMap<Character, Integer>，這里為了效率用的數組for (int right = 0; right < n; right++) {char c = s[right];cnt[c]++;while (cnt[c] > 1) { // 窗口內有重復字母cnt[s[left]]--; // 移除窗口左端點字母left++; // 縮小窗口}ans = Math.max(ans, right - left + 1); // 更新窗口長度最大值}return ans;}
}作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

思路2

class Solution {public int lengthOfLongestSubstring(String S) {char[] s = S.toCharArray(); // 轉換成 char[] 加快效率（忽略帶來的空間消耗）int n = s.length;int ans = 0;int left = 0;boolean[] has = new boolean[128]; // 也可以用 HashSet<Character>，這里為了效率用的數組for (int right = 0; right < n; right++) {char c = s[right];// 如果窗口內已經包含 c，那么再加入一個 c 會導致窗口內有重復元素// 所以要在加入 c 之前，先移出窗口內的 cwhile (has[c]) { // 窗口內有 chas[s[left]] = false;left++; // 縮小窗口}has[c] = true; // 加入 cans = Math.max(ans, right - left + 1); // 更新窗口長度最大值}return ans;}
}作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。