（2）滑动窗口算法练习：无重复字符的最长子串

无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

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

输入: s = "abcabcbb"

输出: 3

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

思路解析：

本题的暴力解法为两层for循环遍历+hash判断是否重复，时间复杂度为O(N^2)，根据暴力解法可以进一步优化将时间复杂度降低到O(N)

以示例数组为例

正向性：定义一个left和一个right指针，二者指向第一个字符。在遍历的过程中，right指针向右移动，直到遇到一个已经出现的字符停止，此时right指针是否需要回退呢？答案是不需要，因为当right指针遇到已经出现过的字符后，left指针就会开始移动，如果left++，则下一个字符为b，此时在区间(left=1)[left, right]中不存在已经重复的字符，因为已经跳过了重复的字符a。所以，left指针和right指针在移动的过程中均满足从左向右移动不回退

在上面的示例中，重复字符为第一个字符，考虑示例：s="deabcabcbb"。在该示例中，right向右移动一直到第二个字符a，此时[left, right]中存在重复字符a，停止移动right，接下来移动left，那么left是否需要一次只移动1个长度呢？不需要，原因很简单，left++后下一个区间(left=1)[left, right]起始字符为e，而对应区间中的子串为eabca，仍然存在重复字符a，所以left在移动时并不是每一次都只移动1个长度（即只循环一次），只需要让left移动到当前区间第一个重复字符的下一个字符b的位置即可，所以需要使用循环来让left一直移动直到跳过重复字符

对于哈希表的处理，不需要使用库中的结构，因为题目中给出了结果s的取值只会出现英文字母、数字、符号和空格，所以只需要定义一个长度为128的数组即可，对应的下标即为对应字符的ASCII码值

根据上面的分析，因为left和right在遍历的过程中不需要回退，所以可以考虑使用滑动窗口算法解决，步骤如下：

1. 进窗口：本题进窗口意味着只要元素没有在哈希表数组中就进入哈希表数组

2. 判断：因为遇到重复的字符right就停止移动，所以当哈希表数组字符ASCII值下标对应的元素不为0即代表重复，作为判断条件

3. 出窗口：出窗口则意味着已经在哈希表中的元素需要离开哈希表，并让left向后移动，需要注意的是，因为需要进入一个新的窗口，所以出窗口时需要使left位置的字符对应哈希数组下标值的元素出现的次数改变

4. 更新结果：本题更新结果只需要在[left, right]区间没有重复字符后即可，用变量len存储子串长度，再移动right

具体步骤如下：

参考代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0}; // 创建hash表
        int len = 0;
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            hash[s[right]]++; // 标记已经出现
            // 判断
            while(hash[s[right]] > 1)
            {
                hash[s[left++]]--;// 出窗口
            }
            len = max(len, right - left + 1);// 更新结果
        }

        return len;
    }
};

原文地址：https://blog.csdn.net/m0_73281594/article/details/140308587

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！