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 length of 1.
Given "pwwkew", 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.

大致意思：給定一個(gè)字符串浊吏，找到其中最大不重復(fù)子串芙粱，返回其長(zhǎng)度。

My View

一開(kāi)始的思路就是暴力解決疆偿，兩個(gè)循環(huán)來(lái)檢查是否滿足條件朵栖，然后就有了下面的代碼

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals("")){
           return 0;    
        }else{
        int count;
        int ecount = 0;
        for(int i = 0;i<s.length(); i++){
            count = 1;
            for(int j = i+1; j < s.length(); j++){
              if(s.substring(i,j).contains(String.valueOf(s.charAt(j)))){
                  break; 
              }
                count++;
            }
         if(count > ecount){
             ecount = count;
         } 
        }
        return ecount;     
    }
  }
}

很可惜怜森，

得到了這樣的結(jié)果邮破，982/983邻吞，最后一組數(shù)據(jù)因?yàn)樘L(zhǎng)齿兔，規(guī)定時(shí)間耗盡萨螺，然后不符合題目要求。
第一反應(yīng)是HashMap愧驱，因?yàn)閯傋鲎鲞^(guò)的第一題優(yōu)解是采用HashMap的慰技，可是搞了半天還是搞不明白，對(duì)Hashmap了解甚少……感覺(jué)Java白學(xué)了组砚，挖個(gè)坑復(fù)習(xí)去吻商。

Solution

solution1

那么下面是官方的solution

To enumerate all substrings of a given string, we enumerate the start and end indices of them. Suppose the start and end indices are ii and jj, respectively. Then we have 0 \leq i \lt j \leq n0≤i<j≤n (here end index jj is exclusive by convention). Thus, using two nested loops with ii from 0 to n - 1n?1 and jj from i+1i+1 to nn, we can enumerate all the substrings of s.
To check if one string has duplicate characters, we can use a set. We iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If so, we return false. After the loop, we return true.

具體的意思就是建立一個(gè)雙層循環(huán)，來(lái)取得子字符串糟红，然后通過(guò)檢查函數(shù)來(lái)檢查此字符串滿不滿足條件艾帐，而檢查函數(shù)的寫(xiě)法是通過(guò)一個(gè)set集合來(lái)儲(chǔ)存被比較值，然后不斷拿比較值來(lái)比較是否存在盆偿。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

可以看到allUnique函數(shù)柒爸，建立一個(gè)數(shù)據(jù)集，然后在比較范圍內(nèi)事扭，沒(méi)有包含字符就添加進(jìn)結(jié)果集捎稚，有包含的話直接返回false。
然后通過(guò)max來(lái)找到最后的最大值。

由于用了三層循環(huán)今野，所以是O(n?3??)的復(fù)雜度葡公，結(jié)果自然是[Time Limit Exceeded]了。

solution2

然后官方第二種solution
Sliding Window(滑動(dòng)窗口)

The naive approach is very straightforward. But it is too slow. So how can we optimize it?

上來(lái)就來(lái)一句：明顯的嘲諷……

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring s_{ij}
?? from index ii to j - 1j?1 is already checked to have no duplicate characters. We only need to check if s[j] is already in the substring s_{ij}

那么這里的意思是条霜，如果我們已經(jīng)檢查了某個(gè)字串不含重復(fù)字符的話催什，就不用在多檢查一次了，而我們用雙層循環(huán)的時(shí)候宰睡，其實(shí)是對(duì)已經(jīng)檢查過(guò)的串又檢查一遍蒲凶。

By using HashSet as a sliding window, checking if a character in the current can be done in O(1).

這里就給出了解決方案，用一個(gè)HashSet集合來(lái)作為一個(gè)滑動(dòng)窗口來(lái)檢查字符串拆内，可以降低我們的復(fù)雜度豹爹，那么突破點(diǎn)也就在這。

A sliding window is an abstract concept commonly used in array/string problems.

那么滑動(dòng)窗口多用來(lái)解決一些數(shù)組或者字符串的問(wèn)題矛纹，是一個(gè)抽象的概念

Back to our problem. We use HashSet to store the characters in current window [i, j) (j ==i initially). Then we slide the index j to the right. If it is not in the HashSet, we slide j further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index ii. If we do this for all ii, we get our answer.

回到問(wèn)題中臂聋，我們用哈希集合來(lái)儲(chǔ)存一個(gè)[i，j)區(qū)間的子串作為一個(gè)窗口或南，然后我們移動(dòng)右邊值孩等，如果發(fā)現(xiàn)的新值不在集合里就接著找，直到找到一個(gè)在集合里已經(jīng)有的值采够，記錄下此時(shí)的不重復(fù)長(zhǎng)度肄方，那么接下來(lái)把窗口左值向右移動(dòng)就可以遍歷完所有的子串。從而最后得到我們的最大值蹬癌。

接下來(lái)代碼

public class Solution {
    public int lengthOfLongestSubstring(String s) {
       //取得字符串長(zhǎng)度 
       int n = s.length();
      //建立HashSet
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        
       //遍歷字符串
        while (i < n && j < n) {
            // try to extend the range [i, j]
           //如果數(shù)據(jù)集不包含查找到的新字符 
           //就把他放到集合里
           if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                //返回可以找到的最大值
                ans = Math.max(ans, j - i);
            }
            else {
               //否則本次查找結(jié)束权她，窗口左邊向右移動(dòng)
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

那么很顯然這個(gè)算法的復(fù)雜度是O(n),那么空間復(fù)雜度的話，是取決于Hash占用的逝薪，當(dāng)然也取決于字符串的長(zhǎng)度隅要。

在這里會(huì)發(fā)現(xiàn)Hash在解決數(shù)組或字符串問(wèn)題上很有用，完全可以替代兩層循環(huán)的復(fù)雜度董济，在下面官方還給了一個(gè)滑動(dòng)窗口改進(jìn)版步清，

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

太深?yuàn)W，慢慢理解吧虏肾。