在做题中学习(44):无重复字符的最长字串

2024-01-08 18:40:46

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

解法:同向双指针————“滑动窗口”

思路:如下图,当right进窗口后,就出现了a重复,所以在left出窗口时时,需要跳到第一个a 后面的位置,窗口才合法,而这个操作可以用哈希表来实现(判断是否重复出现就看哈希表里那个位置是否为1),而因为窗口的滑动需要重新算数,所以出窗口时left值要--。

1.left = 0,right = 0

2.进窗口————先直接进一个

3.判断————判断是否重复出现就看哈希表里那个位置是否为1

4.出窗口+重复判断————哈希表中left所在字符--

5.更新数据—————选出更长的len

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[128]={0};
        int len = 0;
        for(int left = 0,right = 0;right<s.size();)
        {
            //1.进窗口
            hash[s[right]]++;
            //2.循环判断
            while(hash[s[right]]>1)
            {
                //3.出现重复,出窗口
                hash[s[left++]]--;     
            }
            //4.更新结果
            len = max(len,right - left + 1);
            right++;
            
        }
        return len;
    }
};

文章来源:https://blog.csdn.net/yiren_liusong/article/details/135462742
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。