398,双指针求无重复字符的最长子串

398,双指针求无重复字符的最长子串

You should never judge something you don't understand.

你不应该去评判你不了解的事物。

问题描述

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

示例 1:

输入: "abcabcbb"

输出: 3 

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

示例 2:

输入: "bbbbb"

输出: 1

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

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是子串的长度,"pwke" 是一个子序列不是子串。

 

双指针求解

这题要求的是找出一个最长的字符串,并且这个字符串中没有重复的字符。最容易想到的就是双指针,最开始的时候两个指针i和j都指向第一个元素,然后i往后移,把扫描过的元素都放到map中,如果i扫描过的元素没有重复的,就顺便记录一下最大值max,如果i扫描过的元素有重复的,就改变j的位置,要保证j到i之间不能有重复的元素。我们就以pwwkew为例画个图看一下

398,双指针求无重复字符的最长子串398,双指针求无重复字符的最长子串398,双指针求无重复字符的最长子串

我们使用一个map来存储扫描过的元素,其中i指针是一直往右移动的,如果i指向的元素在map中出现过,说明出现了重复的元素,要更新j的值。并且这个j的值只能增大不能减小,也就是说j只能往右移动,不能往左移动,所以下面代码中j取的是重复元素位置的下一个值和j这两个值的最大值,有点绕,我们直接看代码

  •  
if (map.containsKey(s.charAt(i))) {    j = Math.max(j, map.get(s.charAt(i)) + 1);}

再来看下完整代码

 1public int lengthOfLongestSubstring(String s) {
2    if (s.length() == 0)
3        return 0;
4    HashMap<Character, Integer> map = new HashMap<>();
5    int max = 0;
6    for (int i = 0, j = 0; i < s.length(); ++i) {
7        //如果有重复的,就修改j的值
8        if (map.containsKey(s.charAt(i))) {
9            j = Math.max(j, map.get(s.charAt(i)) + 1);
10        }
11        map.put(s.charAt(i), i);
12        //记录查找的最大值
13        max = Math.max(max, i - j + 1);
14    }
15    //返回最大值
16    return max;
17}

使用队列求解

除了使用双指针以外,我们还可以使用队列来解决,这个原理也很简单。就是把元素不停的加入到队列中,如果有相同的元素,就把队首的元素移除,这样我们就可以保证队列中永远都没有重复的元素,每次计算的时候我们都要记录下最大长度,最后再返回即可。

398,双指针求无重复字符的最长子串
 1public int lengthOfLongestSubstring(String s) {
2    //用链表实现队列,队列是先进先出的
3    Queue<Character> queue = new LinkedList<>();
4    int max = 0;
5    for (char c : s.toCharArray()) {
6        while (queue.contains(c)) {
7            //如果有重复的,队头出队,这里通过while循环,
8            //如果还有重复的就继续出队,直到队列中没有
9            // 重复的元素为止
10            queue.poll();
11        }
12        //添加到队尾
13        queue.add(c);
14        //记录下最大长度
15        max = Math.max(max, queue.size());
16    }
17    return max;
18}

注意这里的while循环是不能改为if语句的,因为他移除的不一定都是重复的元素,他移除的是重复元素和他前面的元素。比如pweaw,当遇到第二个w的时候,因为出现了重复,所以我们要先把队首的元素p给移除,然后再把w给移除。

 

总结

这题没什么难度,使用双指针和队列都能很容易解决,代码量也不多,无论使用哪种方式,我们都要保证两个指针之间或者队列中不能出现重复的元素。

 

 

398,双指针求无重复字符的最长子串

397,双指针求接雨水问题

396,双指针求盛最多水的容器

394,经典的八皇后问题和N皇后问题

373,数据结构-6,树

 

 

398,双指针求无重复字符的最长子串

长按上图,识别图中二维码之后即可关注。

 

如果喜欢这篇文章就点个"赞"吧

上一篇:SAP web 开发 (第二篇 bsp 开发 mvc模式 Part1 )


下一篇:Web cookie 详解