画解算法：3. 无重复字符的最长子串（使用List）

题目链接

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

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题方案

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

• 一句话：滑动找到所有不重复的子字符串，如果长度最长，记录为最长字符串。
• 遍历数组，第一个不重复子字符串为最长字符串。
• 如果当前字符不存在于子字符串，加入子字符串，如果当前字符串长度大于最长字符串，当前字符串设为最长字符串。
• 如果存在，则去除子字符串中当前字符及以前的字符，继续遍历。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] arr = s.toCharArray();
        int maxLength = 0;//最长不重复字符串长度
        List<Character> list = new ArrayList<>();//当前相连不重复字符串
        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，可以不再一直维护一个list。其中key用于查看是否重复，value用于记录下一个不重复字符串的开始位置，详情请参考画解算法：3. 无重复字符的最长子串

代码

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;
    }
}

测试用例

输入	" "	"nfpdmpi"	"pwwkew"
输出	1	5	3