題目連結

題型解說

這是一題難度為普通的題目

需要設計一個方法，此方法會傳入一個字串 s

要求是找出字串內連續且不重複的字元的長度

abcabcbb => abc => 3
pwwkew => wke => 3

解題思路

創建一個 List ，並走訪一遍字串

遇到 List 沒有的字元就加入

遇到重複的字元就比較當下最大長度與前面最大長度

並且把重複字元前的所有字元移除

程式碼

Java

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        
        if (s.length() < 2) {
            return 1;
        }
        
        int max = 0;
        
        List<Character> list = new ArrayList<>();
        
        for (char c: s.toCharArray()) {
            int index = list.indexOf(c);
            
            if (index > -1) {
                int size = list.size();
                
                max = Math.max(size, max);
                
                for (int i = 0; i <= index; i++) {
                    list.remove(0);
                }
            }
            
            list.add(c);
        }
        
        return Math.max(list.size(), max);
    }
}

更好的解法

上面是我沒參考答案自己弄出來的一種方式

後來研究其他人提供的解法，找到了更簡略的方式

原本的解法1是利用 List 來幫忙紀錄順序

解法2是創建一個長度256的陣列，預設值為-1

一樣走訪字串，並把字元對應的陣列填入該字元的索引值

相等於 List 的 index，並隨時計算左邊界的位置和最大長度

這麼說可能有點模糊，下面我用圖解的方式來說明

有兩個變數 max 表示最大長度、left 表示左邊界

文字上面的數字表示出現的位置，-1 代表尚未出現

第一個字元

第一步計算左邊界，因為尚未出現重複字元p，故維持 -1

第二步標上位置，p為0

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

0 - (-1) = 1

1 比 0 大，故將 max 改為 1

第二個字元

第一步計算左邊界，因為尚未出現重複字元w，故維持 -1

第二步標上位置，w為1

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

1 - (-1) = 2

2 比 1 大，故將 max 改為 2

第三個字元

第一步計算左邊界，因為出現重複字元w，故將左邊界改為上一個重複字元的位置 1

第二步標上位置，w為2

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

2 - 1 = 1

1 比 2 小，故 max 維持 2

第四個字元

第一步計算左邊界，因為尚未出現重複字元k，故維持 1

第二步標上位置，k為3

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

3 - 1 = 2

2 和 2 一樣大，故 max 維持 2

第五個字元

第一步計算左邊界，因為尚未出現重複字元e，故維持 1

第二步標上位置，e為4

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

4 - 1 = 3

3 比 2 大，故將 max 改為 3

第六個字元

第一步計算左邊界，因為出現重複字元w，故將左邊界改為上一個重複字元的位置 2

第二步標上位置，w為5

第三步，計算最大值，計算方式為 目前索引 減去 左邊界

5 - 2 = 3

3 和 3 一樣大，故 max 維持 3

最終回傳值為 3，若是需要回傳字串本身，答案是 wke 或是 kew 兩種

程式碼

Java

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        
        if (s.length() < 2) {
            return s.length();
        }
        
        int[] temp = new int[256];
        
        Arrays.fill(temp, -1);
        
        int max = 0;
        int left = -1;
        
        for (int i = 0, len = s.length(); i < len; ++i) {
            left = Math.max(left, temp[s.charAt(i)]);
            
            temp[s.charAt(i)] = i;
            
            max = Math.max(max, i - left);
        }
        
        return max;
    }
}