LeetCode_3. 无重复字符的最长子串哈希+滑动窗口+C语言

深藏阁楼爱情的钟 2023-09-28 16:45 80阅读 0赞

### 题目链接： ###

> [3. 无重复字符的最长子串][3.]

### 题目描述： ###

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

### 测试用例： ###

> 示例1:  
> 输入: s = “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

> 示例2：  
> 输入: s = “bbbbb”  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

> 示例3：  
> 输入: s = “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

### 解题思路： ###

> 定义一个left值和right值表示滑动窗口的左右两边，然后再定义一个hash表来记录窗口中的字母，窗口中出现的字母值置为1，没有出现过的置为0，然后进行一次遍历，当遍历到没有出现过的字母时，将hash表中该字母对应的数字置为1表示他出现过了，接着我们将窗口的右边界right++，遍历下一个字母；若遍历到出现过的字母时，则我们需要从滑动窗口的左边界开始寻找该字母在窗口中出现的位置，进行相应的更新，详细可以看代码注释。

### 题解代码： ###

int lengthOfLongestSubstring(char * s){
        
        //定义一个哈希表记录是否出现重复值
        int hash[128]={
        0};
        //计数
        int cnt=0;
        //记录最大程度
        int ret=0;
        //字符串长度
        int len=strlen(s);
        //窗口左右值
        int left=0;
        int right=0;
        //以right为下标进行遍历
        while(right<len){
        
        //如果该字母此前未出现过 则将其在哈希表中的值改为1表示他出现过了
            if(hash[s[right]]==0){
        
                hash[s[right]]=1;
                cnt++;
                right++;
                //更新返回值 确保它是最大的
                ret=ret>cnt?ret:cnt;
            }
            //如果该字母已经出现过了
            else{
        
            //那我们就不动滑动窗口的右值right，将其左值+1
            //左值+1之后我们要记得将在哈希表中的记录改为0
            //即表示左值已经被弹出窗口了 所以哈希表中对应下标置0
                hash[s[left]]=0;
                left++;
            //因为滑动窗口里面的字母少了一个 所以我们的计数值cnt-1
                cnt--;
            }
            //ps：执行完else之后 重写遍历检查了是一个重复的字母 
            //如果依旧重复 则会执行else步骤 直到不重复位置 才会
            //继续往后遍历
        }
        return ret;
    }

[3.]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/