每日leetcode算法题：3. 无重复字符的最长子串

た入场券 2024-03-30 15:33 13阅读 0赞

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

![e79b8945783eca19534ef4e0fb243345.png][]

提示：

0 <= s.length <= 5 * 104
    s 由英文字母、数字、符号和空格组成

**思路：**

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)O(n)

思路和算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。

我们不妨以示例一中的字符串 \\texttt\{abcabcbb\}abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

以 \\texttt\{(a)bcabcbb\}(a)bcabcbb 开始的最长字符串为 \\texttt\{(abc)abcbb\}(abc)abcbb；

以 \\texttt\{a(b)cabcbb\}a(b)cabcbb 开始的最长字符串为 \\texttt\{a(bca)bcbb\}a(bca)bcbb；

以 \\texttt\{ab(c)abcbb\}ab(c)abcbb 开始的最长字符串为 \\texttt\{ab(cab)cbb\}ab(cab)cbb；

以 \\texttt\{abc(a)bcbb\}abc(a)bcbb 开始的最长字符串为 \\texttt\{abc(abc)bb\}abc(abc)bb；

以 \\texttt\{abca(b)cbb\}abca(b)cbb 开始的最长字符串为 \\texttt\{abca(bc)bb\}abca(bc)bb；

以 \\texttt\{abcab(c)bb\}abcab(c)bb 开始的最长字符串为 \\texttt\{abcab(cb)b\}abcab(cb)b；

以 \\texttt\{abcabc(b)b\}abcabc(b)b 开始的最长字符串为 \\texttt\{abcabc(b)b\}abcabc(b)b；

以 \\texttt\{abcabcb(b)\}abcabcb(b) 开始的最长字符串为 \\texttt\{abcabcb(b)\}abcabcb(b)。

发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 kk 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r\_kr k。那么当我们选择第 k+1k+1 个字符作为起始位置时，首先从 k+1k+1 到 r\_kr k 的字符显然是不重复的，并且由于少了原本的第 kk 个字符，我们可以尝试继续增大 r\_kr k，直到右侧出现了重复字符为止。

这样一来，我们就可以使用「滑动窗口」来解决这个问题了：

我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 r\_kr k；

在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

在枚举结束后，我们找到的最长的子串的长度即为答案。

判断重复字符

在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered\_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

至此，我们就完美解决了本题。

class Solution {
        public int lengthOfLongestSubstring(String s) {
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    }

public int lengthOfLongestSubstring(String s) {
            HashMap<Character, Integer> map = new HashMap<>();
            int maxLen = 0;//用于记录最大不重复子串的长度
            int left = 0;//滑动窗口左指针
            for (int i = 0; i < s.length() ; i++)
            {
                /**
                1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
                 此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；
    
                2、如果当前字符 ch 包含在 map中，此时有2类情况：
                 1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
                 那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
                 2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
                 而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
                 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
                 应该不变，left始终为2，子段变成 ba才对。
    
                 为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
                 另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
                 因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
                 */
                if(map.containsKey(s.charAt(i)))
                {
                    left = Math.max(left , map.get(s.charAt(i))+1);
                }
                //不管是否更新left，都要更新 s.charAt(i) 的位置！
                map.put(s.charAt(i) , i);
                maxLen = Math.max(maxLen , i-left+1);
            }
            
            return maxLen;
        }

这是第三次变了：

class Solution \{

publicint lengthOfLongestSubstring(String s) \{

int N = s.length();

int\[\] map = newint\[128\]; // s 由英文字母、数字、符号和空格组成, 包含着ASCII码范围内

Arrays.fill(map,-1); // 初始化 map 所有位置的值为 -1, 作为标记

int start = 0, maxLength = 0, i = 0; // start 纪录当前不重复子串的起始位置, maxLength 纪录最长不重复子串, i 用于扫描字符串 s

while(i < N) \{

char ch = s.charAt(i); // 获取 s\[i\]

Integerindex = map\[ch\]; // 获取 map\[ch\] 上的值

if(index != -1 && index >= start) \{ // 如果 index != -1 (表示 ch 已经添加进map中) && index >= start (表示获取的 ch 是在当前遍历不重复子串的范围内)

maxLength = Math.max(maxLength, i - start); // 更新maxLength, 取较大值

start = index + 1; // 更新 start 为重复字符 ch 所在索引 + 1

map\[ch\] = i; // 更新map\[ch\] 的值, 该位置无论是否已经被赋值都进行更新, 因为两种情况下都需要更新 map\[ch\] 的值

i++; // i 继续向后遍历

return Math.max(maxLength, i - start); // maxLength 只会在进入条件语句后才更新, 如过从 start 开始一直到字符结尾没有发现重复字符, 那么 maxLength将不会再次更新, 所以返回值还需要取 Math.max(maxLength, i - start)

[e79b8945783eca19534ef4e0fb243345.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/32a724a1be1843e9bfffcffdf439d485.png