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

一、题目

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、代码实现

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

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

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;
    }
}

执行结果：

image.png

3、时间复杂度

时间复杂度：O(N)

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

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

三、总结

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

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

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