LeetCode（3）-- 無重複字元的最長子串

題目

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:

輸入: s = “abcabcbb”

輸出: 3

解釋: 因為無重複字元的最長子串是 “abc”，是以其長度為 3。

示例 2:

輸入: s = “bbbbb”

輸出: 1

解釋: 因為無重複字元的最長子串是 “b”，是以其長度為 1。

示例 3:

輸入: s = “pwwkew”

解釋: 因為無重複字元的最長子串是 “wke”，是以其長度為 3。

請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串。

示例 4:

輸入: s = “”

輸出: 0

提示：

0 <= s.length <= 5 * 104

s 由英文字母、數字、符号和空格組成

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

思路以及解答

這是一道滑動視窗的經典題目，也就是有兩個指針，

low

和

high

，同時借助一個

hashmap

,周遊到每一個字元的時候，都要判斷

hashmap

裡面是否已經包含。

• 如果不包含該字元，那麼直接添加進去.
• 如果已經包含該字元，則根據

  key

  取出

  value

  ，也就是它的上一次出現的索引位置。
  • 如果索引位置不在目前的區間[low,high]中，那也是直接

    put

    進去，

    key

    是目前字元，

    value

    是目前的索引。
  • 如果索引位置在目前的區間[low,high]中，則計算目前的不重複字元區間

    high-low

    ，和之前儲存的最大值

    max

    對比，滿足則更新最大值。同時把

    low

    修改為上次出現的字元下一個索引位置。将目前的索引

    high

    字元以及索引添加到

    map

    中。

周遊字元串的每個字元，最後得到的

max

，就是最長字串。

class Solution {public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if(s.length()==1){
            return 1;
        }
        int low = 0;
        int high = 0;
        int max  = 0;
        HashMap<String,Integer> map = new HashMap<>();
        for(;high<s.length();high++){
            String temp = s.charAt(high)+"";
            if(!map.containsKey(temp)){
                map.put(temp,high);
            }else {
                int index = map.get(temp);
                if(index<low){
                    map.put(temp,high);
                }else {
                    max = Math.max(max, (high - low));
                    low = index + 1;
                    map.put(temp, high);
                }
            }
        }
        max = Math.max(max,(high-low));
        return max;
    }}      

【作者簡介】：

秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。寫好每一篇文章，期待和你們一起交流。