【无重复字符的最长子串】

本文主要是介绍【无重复字符的最长子串】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、解决方法

1.暴力解法

解题思路：使用两层循环逐个生成子字符串，再利用es6 new set()去重判断是否有重复字符，若无则比较最大值和不重复字符串长度的大小重新给max_length赋值

2.滑动窗口+哈希

解题步骤和思路：
初始化一个空集合 subSet，用于存储当前窗口中的字符。
初始化右指针 r 为 0，表示窗口的右边界初始位置。
初始化 max_length 为 0，用于记录最长子串的长度。
使用一个循环来移动左指针 i，从 0 到 s.length - 1。
如果 i 不等于 0，说明左指针已经移动过，需要从 subSet 中移除上一个窗口的左边界字符 s.charAt(i-1)。
使用一个内部循环来移动右指针 r，从当前位置开始向右移动，直到 r 达到字符串的末尾或者遇到了一个在 subSet 中已经存在的字符。
在内部循环中，每次移动右指针之前，检查 s.charAt® 是否已经在 subSet 中。如果不在，就将它添加到 subSet 中，并更新 max_length 为当前窗口大小 r - i 和 max_length 中的较大值。
当左指针 i 完成遍历后，max_length 就是最长的不含有重复字符的子串的长度。

这个算法的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。尽管有两个嵌套循环，但是每个字符最多被访问两次（一次由左指针 i 引起，一次由右指针 r 引起），因此整体时间复杂度是线性的。

三、总结

1.es6 new set()的用法

常用于数组去重、用于字符串去重、实现并集、交集、和差集

添加元素add()

删除元素delete()

判断元素是否存在has

……其他用法具体可见http://t.csdnimg.cn/WrM6i

在JavaScript中，Set 是一种集合数据结构，它存储唯一值，并允许快速检查一个值是否在集合中。这种特性使得 Set 非常适合用作哈希集合，用于记录字符是否出现过。

Set 在内部使用哈希表来实现，这提供了一种非常高效的方式来添加、删除和检查元素是否存在。在处理字符串问题时，比如查找无重复字符的最长子串，使用 Set 可以快速判断一个字符是否已经在当前的子串窗口中出现过。

2.滑动窗口和双指针的联系和特点

滑动窗口通常用于解决子数组或子字符串相关的问题，它涉及到一个窗口的左右边界（指针），这个窗口可以在数组或字符串上滑动。滑动窗口的大小可以固定也可以动态变化。

滑动窗口的使用特点：

适用于寻找连续的子数组或子字符串。
窗口的左右边界随着算法的执行而移动。
通常用于需要维护窗口内元素状态的问题。
可以用来解决最大最小问题，如最长子串、最小覆盖子串等。
双指针： 双指针是一种更通用的技术，它可以用于解决多种数组或字符串问题。双指针可以是同向移动、相向移动或背向移动，具体取决于问题的性质。

双指针的使用特点：

适用于配对问题，如两数之和、三数之和等。
可以用于排序数组，快速定位满足条件的元素对。
在某些情况下，双指针可以用来替代滑动窗口，如寻找最长子串时。
双指针可以用于链表问题，如检测循环、找到中间点等。

这篇关于【无重复字符的最长子串】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---