資訊專欄INFORMATION COLUMN
摘要：哈希表是最自然的想法。在遍歷字符串時(shí)，我們先根據(jù)哈希表找出該字符上次出現(xiàn)的位置，如果大于等于子字符串首，便更新子字符串首。結(jié)束后，將該字符新的位置放入哈希表中。
Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/...
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.哈希表雙指針法 Hash Table with Two Pointers 復(fù)雜度
時(shí)間O(n) 空間O(1) 字符種類數(shù)有限
思路根據(jù)最長(zhǎng)不重復(fù)子字符串的定義，我們?cè)诒闅v字符串時(shí)一旦遇到當(dāng)前子字符串中已有字符，那么新的子字符串應(yīng)該從這個(gè)重復(fù)點(diǎn)的下一位開始。所以為了在一次遍歷中就能找出最大長(zhǎng)度，我們需要記錄兩個(gè)東西。第一是某個(gè)字母是否在當(dāng)前子字符串中出現(xiàn)過，第二是如果出現(xiàn)過那它在字符串中的位置是什么。而最簡(jiǎn)單的判斷某個(gè)字符是否在當(dāng)前子字符串中出現(xiàn)過的方法，就是看它上次出現(xiàn)的位置是在當(dāng)前子字符串第一個(gè)字符的前面還是后面，所以我們只要記錄該字符上次出現(xiàn)的位置就可以同時(shí)滿足這兩個(gè)要求。哈希表是最自然的想法。在遍歷字符串時(shí)，我們先根據(jù)哈希表找出該字符上次出現(xiàn)的位置，如果大于等于子字符串首，便更新子字符串首。因?yàn)檫@里相當(dāng)于上一個(gè)子字符串已經(jīng)結(jié)束，我們還要更新最大長(zhǎng)度。結(jié)束后，將該字符新的位置放入哈希表中。
注意遍歷完成后還要有一次額外的更新最大長(zhǎng)度的操作，以處理最長(zhǎng)字符串在末尾的情況。
新的子字符串的起點(diǎn)應(yīng)該是重復(fù)元素的下標(biāo)加一
字符串問題要注意處理空字符串的特例
所記錄的上次出現(xiàn)位置大于等于lowerBound時(shí)就需要更新了，注意這個(gè)last >= lowerBound
代碼public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0){
return 0;
}
Map table = new HashMap();
int lowerBound = 0, max = 1;
for(int i = 0; i < s.length(); i++){
Character c = s.charAt(i);
Integer last = table.get(c);
if(last != null && last >= lowerBound){
max = Math.max(i - lowerBound, max);
lowerBound = last + 1;
}
table.put(c, i);
}
return Math.max(s.length() - lowerBound, max);
}
}
2018/2
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
characters = {}
startIndex = 0
endIndex = 0
maxLen = 0
while endIndex < len(s):
c = s[endIndex]
maxLen = max(maxLen, endIndex - startIndex)
if c in characters and characters[c] >= startIndex:
startIndex = characters[c] + 1
characters[c] = endIndex
endIndex = endIndex + 1
maxLen = max(maxLen, endIndex - startIndex)
return maxLen
后續(xù) Follow Up
Q: 能否不用哈希表完成本題？
A：可以將哈希表換成和字符一一映射的數(shù)組。如果是ASCII字符集，可以初始化一個(gè)256個(gè)元素的數(shù)組，數(shù)組的下標(biāo)對(duì)應(yīng)于字符的ASCII碼，而數(shù)組的內(nèi)容則是每個(gè)字符上次出現(xiàn)的位置。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64392.html
Problem Given a string, find the length of the longest substring without repeating characters. Examples Given abcabcbb, the answer is abc, which the length is 3. Given bbbbb, the answer is b, with the...
摘要：建立數(shù)組，存儲(chǔ)個(gè)字符最近一次出現(xiàn)的位置。首次出現(xiàn)某字符時(shí)，其位置標(biāo)記為，并用無重復(fù)字符計(jì)數(shù)器記錄無重復(fù)字符的長(zhǎng)度，再在更新其最大值。循環(huán)完整個(gè)字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...
摘要：題目詳情題目要求輸入一個(gè)字符串，我們要找出其中不含重復(fù)字符的最長(zhǎng)子字符串，返回這個(gè)最長(zhǎng)子字符串的長(zhǎng)度。對(duì)于字符串中的每一個(gè)字符，先判斷中是否已經(jīng)存在這個(gè)字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個(gè)字符的地方開始。 題目詳情 Given a string, find the length of the longest substring without repe...
摘要：哈希表法雙指針法只有當(dāng)也就是時(shí)上面的循環(huán)才會(huì)結(jié)束，，跳過這個(gè)之前的重復(fù)字符再將置為 Problem Given a string, find the length of the longest substring without repeating characters. Example For example, the longest substring without repeat...
摘要：解題思路本題借助實(shí)現(xiàn)。如果字符未出現(xiàn)過，則字符，如果字符出現(xiàn)過，則維護(hù)上次出現(xiàn)的遍歷的起始點(diǎn)。注意點(diǎn)每次都要更新字符的位置最后返回時(shí)，一定要考慮到從到字符串末尾都沒有遇到重復(fù)字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...
閱讀 1063·2021-11-24 09:39
閱讀 3602·2021-11-22 13:54
閱讀 2558·2021-10-11 10:59
閱讀 796·2021-09-02 15:40
閱讀 1036·2019-08-30 15:55
閱讀 1053·2019-08-30 13:57
閱讀 2314·2019-08-30 13:17
閱讀 3034·2019-08-29 18:32
