leetcode熱題系列之無重複字元的最長字串（003）

3. 無重複字元的最長子串

題目和示例：

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

示例 1:

輸入: “abcabcbb”

輸出: 3

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

示例 2:

輸入: “bbbbb”

輸出: 1

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

示例 3:

輸入: “pwwkew”

輸出: 3

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

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

來源：力扣（LeetCode）

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

思路：

1. 首先隻要有關于重複的字眼，都要思考是否能用上HashMap這個資料結構。

具體來說，這個是存在字元的下一個位置（很好了解，既然 ‘我’ 都重複了 當然要從下一個位置開始）

3. 這裡用到了TCP的滑動視窗的思想。

具體做法：

1. 首先定義視窗的左右指針 left right

2. right一步一步往右邊走

3. 每當遇到一個字元我們就要判斷這個字元是不是在hashmap當中

4. 若是 重新判斷起點：究竟是維持原起點還是更新Hashmap的值？

比如：abba 當left在第二個b right走到a的時候 left當然不會傳回第一個b。

是以我們隻需要在這裡加一個Math.max()即可。

5. 邊走的同時也要更新ans的結果。

代碼：

package Hot003;

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int ans = 0;
        HashMap<Character,Integer> hashMap = new HashMap<>();
        
        for(int left = 0,right = 0; right<length;right++){
            char temp = s.charAt(right);
            if(hashMap.containsKey(temp)){ //重複
                left = Math.max(hashMap.get(temp),left);
            }
            ans = Math.max(ans,right-left+1);
            hashMap.put(temp,right+1);
        }
        return ans;
    }
}
           

github位址：

https://github.com/CLFlemon/LeetcodeHot100