題目

給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例

示例1

輸入: s = “abcabcbb”
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “abc”，所以其長(zhǎng)度為 3。

示例2

輸入: s = “bbbbb”
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “b”，所以其長(zhǎng)度為 1。

示例3

輸入: s = “pwwkew”
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “wke”，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，“pwke” 是一個(gè)子序列，不是子串。

解題

解法1

粗暴破解，找一個(gè)最長(zhǎng)子串，那么我們用兩個(gè)循環(huán)窮舉所有子串，然后再用一個(gè)函數(shù)判斷該子串中有沒(méi)有重復(fù)的字符。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring1(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring1(String s) {int n = s.length();int len=0;for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {if (unique(s,i,j)){len = Math.max(len,j-i+1);}}}return len;}public static boolean unique(String s, int start, int end) {Set<Character> set = new HashSet<>();for (int i = start; i <= end; i++) {if (set.contains(s.charAt(i))){return false;}set.add(s.charAt(i));}return true;}

解法2

上邊的算法中，我們假設(shè)當(dāng) i 取 0 的時(shí)候，

j 取 1，判斷字符串 str[0,1) 中有沒(méi)有重復(fù)的字符。

j 取 2，判斷字符串 str[0,2) 中有沒(méi)有重復(fù)的字符。

j 取 3，判斷字符串 str[0,3) 中有沒(méi)有重復(fù)的字符。

j 取 4，判斷字符串 str[0,4) 中有沒(méi)有重復(fù)的字符。

做了很多重復(fù)的工作，因?yàn)槿绻?str[0,3) 中沒(méi)有重復(fù)的字符，我們不需要再判斷整個(gè)字符串 str[0,4) 中有沒(méi)有重復(fù)的字符，而只需要判斷 str[3] 在不在 str[0,3) 中，不在的話，就表明 str[0,4) 中沒(méi)有重復(fù)的字符。

如果在的話，那么 str[0,5) ，str[0,6) ，str[0,7) 一定有重復(fù)的字符，所以此時(shí)后邊的 j 也不需要繼續(xù)增加了。i ++ 進(jìn)入下次的循環(huán)就可以了。

此外，我們的 j 也不需要取 j + 1，而只需要從當(dāng)前的 j 開始就可以了。

判斷一個(gè)字符在不在字符串中，我們需要可以遍歷整個(gè)字符串，遍歷需要的時(shí)間復(fù)雜度就是 O（n），加上最外層的 i 的循環(huán)，總體復(fù)雜度就是 O（n2）。我們可以繼續(xù)優(yōu)化，判斷字符在不在一個(gè)字符串，我們可以將已有的字符串存到 Hash 里，這樣的時(shí)間復(fù)雜度是 O（1），總的時(shí)間復(fù)雜度就變成了 O（n）。

當(dāng) j 指向的 字符 存在于前邊的子串中，此時(shí) i 向前移到 b ,此時(shí)子串中仍然含有字符，還得繼續(xù)移動(dòng)，所以這里其實(shí)可以優(yōu)化。我們可以一步到位，直接移動(dòng)到子串的位置的下一位！

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring2(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring2(String s) {int n = s.length();int len = 0;Map<Character, Integer> map = new HashMap<>();for (int i = 0, j = 0; j < n; j++) {if (map.containsKey(s.charAt(j))) {i = Math.max(i, map.get(s.charAt(j)));}map.put(s.charAt(j), j + 1);len = Math.max(len, j - i + 1);}return len;}
}

leetcode

leetcode地址