☆打卡算法☆LeetCode 3、求不重复字符的字符串长度 算法解析

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 1、算法题目

“找到字符串中，不含有重复字符的字符串的长度。”

题目链接：

来源：力扣（LeetCode）

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

### 2、题目描述

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

比如：

> s = “abcabcbb”

> 输出：3

> 因为无重复字符的最长子串"abc"，所有长度为3。

## 二、解题

### 1、思路分析

这道题是要找出字符串中不重复的子串的长度，所以就是从起始位置 k 出发，找到重复字符为止，这个位置就是最长的结束位置 rk 。

然后下一轮从 k+1 位置出发，继续增大 rk ，直到右侧出现了重复字符为止。

这里使用【滑动窗口】来解决这个问题，那么什么是【滑动窗口】呢，其实就是一个队列，比如例子中的 abcabcbb，进入这个队列（窗口）为abc满足题目要求，当下一个字符a进入队列，变成abca，这时候就不满足要求，所以，就移动（滑动）这个队列（窗口）。

将队列的左元素移除，直到满足题目要求，维持这个队列，找出队列出现最长的长度的时候，求出解！

### 2、代码实现

遍历字符串时，需要用到两个指针，两个指针起始点都在原点，并且在一前一后地向终点移动，两个指针夹着的子串就像一个窗口，窗口大小和覆盖范围会随着两个指针变化。

通过左右指针移动遍历字符串，寻找满足特定条件的连续子区间。

```csharp

public class Solution

{

​ public int LengthOfLongestSubstring(string s)

​ {

​ HashSet<char> letter = new HashSet<char>();// 哈希集合，记录每个字符是否出现过

​ int left = 0,right = 0;//初始化左右指针，指向字符串首位字符

​ int length = s.Length;

​ int count = 0,max = 0;//count记录每次指针移动后的子串长度

​ while(right < length)

​ {

​ if(!letter.Contains(s[right]))//右指针字符未重复

​ {

​ letter.Add(s[right]);//将该字符添加进集合

​ right++;//右指针继续右移

​ count++;

​ }

​ else//右指针字符重复，左指针开始右移，直到不含重复字符（即左指针移动到重复字符(左)的右边一位）

​ {

​ letter.Remove(s[left]);//去除集合中当前左指针字符

​ left++;//左指针右移

​ count–;

​ }

​ max = Math.Max(max,count);

​ }

​ return max;

​ }

}

```

执行结果：

### 3、时间复杂度

时间复杂度：O(N)

其中N是字符串的长度，左右指针分别遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在[0,128) 内的字符，即∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣ 个，因此空间复杂度为O(∣Σ∣)。

## 三、总结

这段代码将数组放入HashSet中，记录数据的字符，将字符串中的位置储存在一起。

在进行循环时，发现重复字符，取得这个字符在字符串中的位置，然后再开头时将所有在他前面的字符中移除，可以减少第二层循环中的判断次数。

考虑从HashSet中移除元素，同样需要从当前位置到重复位置的循环来进行HashSet的移除，所以多进行了几次循环，但是第二次循环中就可以不用去判断，也在一定程度上减少了时间的浪费。