LeetCode3. [M]无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

思路

使用滑动窗口，以abcabcbb为例：

第一个窗口为abc此时继续滑动，a将进入队列，此时变为abca不符合无重复字符得条件
此时将a从窗口中移除，窗口变为bca，满足条件

关键在于，每次窗口中加入一个新的字符，就去判断窗口中是否有重复字符，如果有我们就移动left，直到窗口中没有与新字符重复的元素

ps:重复元素可能是窗口中的任意一个

代码

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        if (s.size() == 0)
            return 0;
        //HashSet
        unordered_set<char> set;
        //left代表窗口得最左侧
        int left=0,ans=0;
        for(int i=0;i<s.size();i++)
        {
            //每当窗口进入一个新元素，就去判断是否存在重复元素，只要存在就移动窗口左边界，直到没有重复字符。
            while(set.find(s[i])!=set.end())
            {
                set.erase(s[left]);
                left++;
            }
            ans=max(ans,i-left+1);
            //加入到集合（窗口），事实上set中存储得字符就是窗口中包含的字符。
            set.insert(s[i]);
        }
        return ans;
    }
};

滑动窗口基本模板

//这是一段在网上看到的滑动窗口模板
int func(vector<int>& nums)
{
    int left=0,right=0,var=0,len=nums.size(),ans=0;
    while (right<len)
    {
        //用nums[right]更改var变量
        while (不满足条件)
        {
            //用nums[left]来更新var变量
            left++;
        }
        if (xxxxxx) ;//更新最优结果ans
        right++;
    }
}

以下代码为基于上述模板编写，整体思想其实没有变化，但这种写法更类似于双指针，可作为参考

int lengthOfLongestSubarray(vector<int>& nums) {
    int left = 0, right = 0; // 初始化左右指针
    int len = nums.size(), ans = 0; // 获取数组长度和最优结果
    unordered_set<int> set; // 用于存储当前窗口中的元素

    while (right < len) {
        // 用 nums[right] 更改 var 变量
        // 当集合中存在重复元素时，移动左指针
        while (set.find(nums[right]) != set.end()) { // 如果当前元素已存在于集合中
            set.erase(nums[left]); // 移除左指针指向的元素
            left++; // 移动左指针
        }

        // 插入当前元素到集合
        set.insert(nums[right]); // 将当前元素加入集合

        // 更新最优结果 ans
        ans = max(ans, right - left + 1); // 更新最长子数组长度
        right++; // 移动右指针
    }

    return ans; // 返回最长子数组的长度
}

结语

无重复字符的最长子串是笔者接触的第一个滑动窗口代码，个人感觉其与双指针有些类似，知识指针移动的条件有所特化。本文由个人笔记修改而来，如有错误，敬请斧正！

参考

3. 无重复字符的最长子串 - 力扣（LeetCode）

‍

这篇文章介绍了LeetCode第3题“无重复字符的最长子串”的解题思路和代码实现。文章首先通过示例说明滑动窗口的工作原理：当窗口中出现重复字符时，移动左边界直至无重复。随后提供了两种代码实现方式：一种是基于哈希集合的滑动窗口解法，另一种是更通用的滑动窗口模板。最后指出该问题与双指针方法的相似性，并欢迎读者指正错误。

LeetCode3. [M]无重复字符的最长子串