3.无重复字符的最长子串

发表于 | 分类于 | 阅读次数

题目

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

题解

1、使用List

  • list.contains()
  • list.add()：遍历每个字符，若list中不存在，加入进列表。
  • list.indexOf()：若list中已存在此字符，获取此字符的index，需要将<=该index的字符们从list中移除。
  • list.subList(int fromIndex, int toIndex)
  • list.removeAll()

示例

  • s=”advdf”；
  • list变化：(a)->(a,d)->(a,d,v)->(v,d)->(v,d,f)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
        char[] arr = s.toCharArray();
        List<Character> list = new ArrayList<>();
        int lengthOfLongest = 0; //所记长度-初始0
        for (int i = 0; i < arr.length; i++) {
            Character word = arr[i];
            if (list.contains(word)) {
                // 获取list中该字符的index
                int indexOfRepeatedChar = list.indexOf(word);
                // 截取list中该字符的index及之前索引的字符列表
                List<Character> needToRemoveChars = list.subList(0, indexOfRepeatedChar + 1);
                // 从list中去除
                list.removeAll(needToRemoveChars);
                // 注：此处不用更新lengthOfLongest，因为删除数量 >= 增加数量(为1)
                list.add(word);
            } else {
                list.add(word);
                // 若所记长度<列表长度，取列表长度。否则，所记长度不变
                lengthOfLongest = lengthOfLongest < list.size() ? list.size() : lengthOfLongest;
            }
        }
        return lengthOfLongest;
    }

时间复杂度：O(n)，空间复杂度：O(n,m):取决于字符串 n 的大小以及字符集/字母 m 的大小。

2、滑动窗口+HashMap

滑动窗口是数组/字符串问题中常用的抽象概念。窗口[i,j)：由i和j两个索引边界定义的元素集合，若都向右滑动一个元素->[i+1,j+1)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, result = 0;
        // map用来装不重复的字符，并不做remove操作，用来记录字符-索引映射关系以及使用containsKey()
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0; end < s.length(); end++) {
            Character currentChar = s.charAt(end);
            if (map.containsKey(currentChar)) {
                // 若有重复元素，窗口左区间需判断：是否需要右移至重复元素的索引后一位
                start = Math.max(map.get(currentChar) + 1, start);
            }
            // 每次遍历都会将currentChar放进map
            map.put(currentChar, end);
            // end-start+1为当前窗口字符数量
            result = Math.max(result, end - start + 1);
        }
        return result;
    }
}

关键点

  • 滑动窗口[start,end]，初始[0,0],每次遍历end+1，窗口长度=end-start+1;
  • 若map中存在重复元素，start要做判断：若map中重复元素的索引后一位在当前start向左，并不移动窗口,start不变。

例如：”qwefewjk”，遍历至第二个w时，此时start=f处索引3，start并不会变成map中w索引1。

  • 每次遍历都要将遍历字符做key，索引做value放进map。map主要用来判断字符是否有重复，并获取最近重复的索引。

题目：力扣No.3-无重复字符的最长子串