Java web算法

找出字符串中不含重复字符的最长子串的长度

2020-04-10  本文已影响0人  程序猿蛋蛋哥

1. 题目

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

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

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

示例3:
输入:"pwwkew"
输出:3
解释:因为无重复字符的最长子串是:"wke"或"kew",所以其长度为3
注意:必须是子串的长度,子串是连续的字符,中间不能跳跃字符,如"pwke"是一个子系列,不是子串。

2. 解题思路

2.1 思路一:滑动窗口

窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即[i, j)(左闭,右开),而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

例如:
我们将[i, j)向右滑动1个元素,则它将变为[i+1, j+1)(左闭,右开)
HashSet存储当前处于窗口[i, j)(最初 j = i)中的字符,然后我们向右滑动索引j,如果它不在HashSet中,我们会继续滑动j,直到s[j]已经存在于HashSet中,此时没有重复的最长子字符串将会以索引i开头

HashSet存放当前处于滑动窗口中的字符,初始HashSet为空。
窗口的左边i不动,右边j向右滑动,依次遍历字符:j为指向字符的索引。
当j = 0时,遍历字符p,加入HashSet -- [p],则目前无重复字符的最大子串长度maxSubLength = 1
当j = 1时,遍历字符w,加入HashSet -- [p, w],则maxSubLength = 2

滑动窗口1.png

当j = 2时,遍历字符w,此时HashSet中已包含重复字符w,
则窗口的左边i向右滑,右边j不动,HashSet依次删除索引i所指向的字符,直到HashSet不再包含该字符w,
然后重新将遍历字符w加入HashSet中,启动窗口j继续右滑。

滑动窗口2.png

窗口的左边i不动,右边j继续向右滑动,依次遍历字符:j为指向字符的索引
当j = 3时,遍历字符k,加入HashSet -- [w k]
当j = 4时,遍历字符e,加入HashSet -- [w k e],则此时maxSubLength = 3

滑动窗口3.png

当j = 5时,遍历字符w,此时HashSet中已包含重复字符w,
则窗口的左边i向右滑,右边j不动,HashSet依次删除索引i所指向的字符,直到HashSet不再包含该字符w,
然后重新将遍历字符w加入HashSet中,启动窗口j右滑。
结束,则maxSubLength = 3

滑动窗口4.png

代码实现:

public static int lengthOfLongestSubstring(String s) {
    if (s == null || "".equals(s)) {
        return 0;
    }
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int maxLength = 0;
    int i = 0;
    int j = 0;
    while (i < n && j < n) {
        if (!set.contains(s.charAt(j))) {
            set.add(s.charAt(j++));
            maxLength = Math.max(j - i, maxLength);
        } else {
            set.remove(s.charAt(i++));
        }
    }
    return maxLength;
}

2.2 思路二:优化的滑动窗口

针对上述的滑动窗口方法,不使用集合来判断一个字符是否存在,而定义字符到索引的映射map。
当找到重复字符时,可以立即跳过该窗口。

如果在[i, j)范围内有与s[j]重复的字符,索引为j',即[i, ... j', ... j)
我们不需要逐渐增加i,可以直接跳过[i, j']范围内的所有元素,并将i变为j' + 1

举例:
s = "pwwkew",当 j = 2时,窗口[0, 2)范围内有与s[2]重复的字符w,索引为1(j' = 1),我们可以直接跳过[0, 1]范围内的所有元素,将i变为2(j' + 1)

代码实现:

public static int lengthOfLongestSubstring(String s) {
  if (s == null || "".equals(s)) {
        return 0;
    }
    int n = s.length();
    Map<Character, Integer> map = new HashMap<>(16);
    int maxLength = 0;
    for (int i = 0,j = 0; j < n; j++) {
        if (map.containsKey(s.charAt(j))) {
            i = Math.max(map.get(s.charAt(j)), i);
        }
        maxLength = Math.max(maxLength, j - i + 1);
        map.put(s.charAt(j), j + 1);
    }
    return maxLength;
}

2.3 思路三:使用列表List存储不重复字符

依次遍历字符串 s 中的每次字符,若不是重复字符,加入一个列表list中,若是重复字符,则删除列表list中该重复字符以及前面的所有字符,然后再将该重复字符加入此列表list中。

在遍历的过程中统计出列表list中存储的最大字符个数,即为字符串 s 中不含重复字符的最长子串的长度。

代码实现

public static int lengthOfLongestSubstring(String s) {
    if (s == null || "".equals(s)) {
        return 0;
    }
    List<Character> list = new ArrayList<>();
    int n = s.length();
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        int index = list.indexOf(s.charAt(i));
        if (index == -1) {
            list.add(s.charAt(i));
            maxLength = Math.max(list.size(), maxLength);
        } else {
            for (int j = index; j >= 0; j--) {
                list.remove(j);
            }
            list.add(s.charAt(i));
        }
    }
    return maxLength;
}
上一篇下一篇

猜你喜欢

热点阅读