題目鏈接

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

題目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

解題方案

思路1：使用List（首先想到的方法）

• 一句話：滑動(dòng)找到所有不重復(fù)的子字符串，如果長(zhǎng)度最長(zhǎng)，記錄為最長(zhǎng)字符串。
• 遍歷數(shù)組，第一個(gè)不重復(fù)子字符串為最長(zhǎng)字符串。
• 如果當(dāng)前字符不存在于子字符串，加入子字符串，如果當(dāng)前字符串長(zhǎng)度大于最長(zhǎng)字符串，當(dāng)前字符串設(shè)為最長(zhǎng)字符串。
• 如果存在，則去除子字符串中當(dāng)前字符及以前的字符，繼續(xù)遍歷。

代碼

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] arr = s.toCharArray();
        int maxLength = 0;//最長(zhǎng)不重復(fù)字符串長(zhǎng)度
        List<Character> list = new ArrayList<>();//當(dāng)前相連不重復(fù)字符串
        for (int i = 0; i < arr.length; i++) {

            if (!list.contains(arr[i])) {
                list.add(arr[i]);
                if (list.size() >= maxLength) {
                    maxLength = list.size();
                }
            } else {
                int index = list.indexOf(arr[i]);
                List<Character> needToRemoveChar = list.subList(0, index + 1);
                list.removeAll(needToRemoveChar);
                list.add(arr[i]);
            }
        }
        return maxLength;
    }
}

畫解

1.png

2.png

3.png

4.png

5.png

6.png

7.png

8.png

思路2：使用Map

如果使用Map，可以不再一直維護(hù)一個(gè)list。其中key用于查看是否重復(fù)，value用于記錄下一個(gè)不重復(fù)字符串的開始位置，詳情請(qǐng)參考畫解算法：3. 無重復(fù)字符的最長(zhǎng)子串

代碼

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}

測(cè)試用例