題目

給定一個字符串?s?，請你找出其中不含有重復字符的?最長連續子字符串?的長度。

示例?1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子字符串是 "abc"，所以其長度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子字符串是 "b"，所以其長度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是?"wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。

示例 4:

輸入: s = ""
輸出: 0

提示：

• 0 <= s.length <= 5 * 104
• s?由英文字母、數字、符號和空格組成

哈希表的實現

在遍歷字符串的同時，使用HashMap記錄將字符與字符出現的下標，當遍歷到不存在哈希表中的字符時，說明該字符不是一個重復的，可以記錄在當前長度。如果出現在當前哈希表中，說明是個重復字符，下一次記錄長度應該在該字符的下一個位置進行重新記錄。

具體實現代碼如下

class Solution {public int lengthOfLongestSubstring(String s) {if(s.equals("")){return 0;}//采用hash表解決int begin = 0;int maxLength=0;HashMap<Character,Integer> map = new HashMap();for(int end =begin;end<s.length();end++){char ch = s.charAt(end);if(map.containsKey(ch)){//如果哈希表中已經存在了該字符，那么開始下一次的查找//這里采用max方法是為了避免begin以及指向了下標為2的字符，但map中還存儲著下標為1的字符//當end走到下標為1的相同字符時，begin回退的情況begin = Math.max(map.get(ch)+1,begin);map.put(ch,end);}else{//如果不存在，那么將該字符存放在哈希表中。map.put(ch,end);}maxLength = Math.max(maxLength,end-begin);}return maxLength+1;}
}

數組的實現

因為題目說到了字符串中只包含英文、空格、符號與數字，總共加起來只有128個字符，因此我們可以采用數組來實現，數組長度為128，不同的字符ascii碼值作為下標，字符上一次出現的位置作為數組中存儲的值。

具體實現代碼如下。

class Solution {public int lengthOfLongestSubstring(String s) {//采用數組if(s.equals("")){return 0;}//因為題目中已經確認了字符有哪些，只有128個int[] array = new int[128];//將所有的位置填充-1Arrays.fill(array,-1);int begin =0;int maxLength=0;for(int end = 0;end<s.length();end++){char ch = s.charAt(end);if(array[ch]!=-1){//說明該字符以及出現過了begin = Math.max(begin,array[ch]+1);//記錄最后一次出現的位置array[ch] = end;}else{//說明數組中不存在該元素array[ch] = end;}maxLength = Math.max(maxLength,end-begin);}return maxLength+1;}
}