https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

內容描述：

Given a string, find the length of the longest substring without repeating characters.Example 1:Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3:Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

這個問題的特點就是字符序列不能出現重復，一旦出現重復，比如說w字母出現了兩次，就要比較w出現第一次和第二次這段區間之內的字符串和原來的字符串之間哪個字符串更長，并更新最長字符串。

我們可以定義一個集合，設置一個start指針，一個end指針。res表示的最長字符串的長度。end指針每次都往后移動一個字符，然后判斷這個指針是否在集合里面，如果不在集合里面，就把end指針指向的字符添加到集合里面，并且更新最長字符標識res。

如果end指針中的值出現在集合之中了，就說明出現了重復字符。這時候就應該把start指針往后移動到該字符第一個出現的位置，比較res中的值和新移動的值哪個更大一些，然后更新res。

這里存在一個問題，start指針，一個一個往后移動效率有點低，可不可以一次就定位到指定的位置？答案是可以的，這時候就不能用集合了，可以使用字典的鍵值對的辦法來進行一次定位。但是這樣也有一個很難操作的問題，比如說，對于abcabc而言，當end指針移動到第二次出現a的時候，這個時候，start指針如果也指向end指針一樣的位置的話，當下一次end指針移動到b的時候，會面臨字典中第一次出現的b無法刪除的情況。

事實上，沒有這么麻煩，我們的想法很簡單，我們其實是想，比如說字母c當第二次出現的時候，那么我們start指針指向字母c第一次出現下一個位置就好了。明白這樣的思路，代碼寫起來就很簡單了。

class Solution:def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""# start 指針指向的是當前子串首字符在 input 中對應的indexres, start, n = 0, 0, len(s) maps = {}for i in range(n):start = max(start, maps.get(s[i], -1) + 1) # get方法返回第一次重復字符出現的位置，這樣我們向后+1就是希望start的位置了res = max(res, i - start + 1) # 當前子串滿足條件了，更新結果maps[s[i]] = i # 將當前字符與其在 input 中的 index 記錄下來return res

總結

以上是生活随笔為你收集整理的LeetCode:3. Longest Substring Without Repeating Characters的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。