LeetCode-3 无重复字符的最长子串

Leefs 2020-02-17 PM 1843℃ 0条

# LeetCode-3 无重复字符的最长子串

- 难度：中等
- 分类：字符串
- 解决方案：双指针、滑动窗口

### 题目描述

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

**示例1：**

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

**示例2：**

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

**示例3：**

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

### 分析

首先我们看看这个题的示例3，该示例中提示我们这个题需要求的字符串的**子串**而不是**子序列**，我们具体来看看什么是子串，什么是子序列。

子串：字符串中任意个**连续**的字符组成的子序列称为该串的子串。注意子串强调字符的连续性。

![34.LeetCode-3 无重复字符的最长子串01.png][1]

子序列：字符串中去掉任意个元素后得到的结果即为该字符串的子序列。注意子序列中字符出现的次序与原字符串中字符出现的次序要保持一致。

![34.LeetCode-3 无重复字符的最长子串02.png][2]

区分子串和子序列后，我们再回过头来看看这个题。我们先动手画一画示例1的解题过程，如下图所示：

![34.LeetCode-3 无重复字符的最长子串03.png][3]

从上图我们可以观察出，可以使用双指针（`left`指针和`right`指针）来维护一个滑动窗口，这个窗口内的字符都是没有重复的，遍历一趟字符串后就可以得到最大的子串，因此时间复杂度为`O(n)`。现在想一个问题：**`right`指针指向的字符怎么确定它在前面是否出现过，若出现过，它出现的位置在哪儿？**对于这个问题，做过LeetCode-1 两数之和这道题的小伙伴们应该知道，我们可以使用`HashMap`记录一个字符是否出现以及出现后的位置。对于重复多次出现的字符，我们是保留所有出现的位置还是只记录一个位置？观察示例1分析过程可以知道，我们只需要保存一个最大位置即可。还有一个关键点，我们如何确定`left`指针的位置？这一点非常重要，需要分情况讨论。

+ 1.当目前`right`指针指向的字符未出现过，`left`指针不需要移动；

+ 2.当目前`right`指针指向的字符出现过，如果该字符在窗口中，即该字0符出现在当前`left`指针的右边，则通过`HashMap`获取字符的位置并向右移动一位即为更新后`left`的位置；如果该字符在窗口外面，即在当前`left`指针的左边，则不需要移动`left`的位置。

分析完后，再看看`java`代码的具体实现：

```java
class Solution {
  public int lengthOfLongestSubstring(String s) {
      int res = 0;
      if(s.length() == 0)
          return res;
      // 创建HashMap，用来保存字符与位置之间的对应关系
      HashMap<Character, Integer> hashMap = new HashMap<>();
      // 初始化左指针和右指针，并遍历字符串
      for(int left = 0, right = 0; right < s.length(); right++){
          // 判断右指针指向的字符是否出现过
          if(hashMap.containsKey(s.charAt(right))){
              // 确定左指针的位置
              left = Math.max(left, hashMap.get(s.charAt(right))+1);
          }
          // 对于第一次出现的字符，保存该字符的位置；对于多次出现的字符，更新该字符出现的位置
          hashMap.put(s.charAt(right), right);
          // 更新窗口的大小，保存最大的窗口大小
          res = Math.max(res, right-left+1);
      }
      return res;
  }
}
```

附：[原文链接](https://www.nowcoder.com/discuss/196946)

[1]: https://lilinchao.com/usr/uploads/2020/02/692013184.png
  [2]: https://lilinchao.com/usr/uploads/2020/02/2390713761.png
  [3]: https://lilinchao.com/usr/uploads/2020/02/4004786084.png

标签: LeetCode刷题

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/620.html

上一篇数据结构和算法学习--二叉排序树

下一篇【转载】volatile关键字简介

LeetCode-3 无重复字符的最长子串

评论已关闭

栏目分类

标签云

友情链接申请

LeetCode-3 无重复字符的最长子串

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请