leetcode--3. 无重复字符的最长子串[滑动窗口\哈希表 c++]

2023-12-14 15:11:35

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

题目解析:

最长子串可以用滑动窗口解决,无重复字符可以使用哈希表解决。

算法原理:

滑动窗口+哈希表

哈希表作为一个数组存放每个字符出现的次数。

滑动窗口四步走

1.进窗口

2.判断

3.出窗口

4.更新状态

进窗口 --- 利用哈希表记录进入窗口的字符,即right指向的字符。因为字母有对应的ascii码值,可以转化为int类型,所以直接将字符作为哈希表的下标。

判断 --- 在滑动窗口的判断阶段,若哈希表中存放的数字大于1,则说明当前right指向的字符重复

出窗口---直到left指针跳过了和right指针相同的字符

更新状态---此时right指针指向的字符的哈希表数据更新为1,表明不再重复,继续遍历。

因为left和right都一直向前遍历,所以是同向双指针,即滑动窗口

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};
        int n = s.size(), left = 0,right = 0,ret = 0;
        while(right <n)
        {
            //进窗口
            hash[s[right]]++;
            //判断
            while(hash[s[right]] > 1)
            {
                //出窗口
                hash[s[left++]]--;
            }
            //更新
            ret = max(ret,right-left+1);
            right++;
        }
return ret;
    }
};

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