每日一题2023.12.14|LeetCode3.无重复字符的最长子串

leetcode3.无重复字符的最长字串

连接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

滑动窗口

找出字符串中不含重复字符的最长子串，由于最长子串是连续的，所以可以利用滑动窗口来做。窗口内的字符都是连续的，只需计算窗口内满足要求的最长的子串。
不重复，可以利用哈希表记录字符出现的次数；或者集合存储不重复的字符。

哈希表hashtable

哈希表记录窗口内字符对应的次数
移动窗口的右边界，将右边界对应的字符加入哈希表，
如果该字符对应的次数大于1，就移动左边界，将左边界对应的字符的个数减1，直到右边界对应的字符个数为1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //哈希表map
        unordered_map<char,int>ma;
        int l=0,ans=0;
        for(int r=0;r<s.size();++r){
            ma[s[r]]++;
            while(l<s.size()&&ma[s[r]]>1){
                ma[s[l]]--;
                l++;
            }
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};

func lengthOfLongestSubstring(s string) int {
    ma:=make(map[uint8]int)
    l,r,ans:=0,0,0//l,r滑动窗口左右边界,ans记录答案
    for ;r<len(s);r++{
         ma[s[r]]++
         for ma[s[r]]>1{
             ma[s[l]]--
             l++
         }
         ans=max(ans,r-l+1)
    }
    return ans
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

集合set

用集合存储窗口内出现的字符
移动窗口右边界，右边界对应的字符如果没有出现在集合中就加入集合；如果右边界对应的字符出现在集合中，就移动左边界，如果左边界对应的字符与右边界对应的字符不相等，就将左边界对应的字符从集合中删除，如果左边界对应的字符与右边界对应的字符相等就只移动左边界不需删除[因为右边界对应的字符与左边界对应的字符一致但是并没有将右边界对应的字符加入集合]

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //set
        unordered_set<char> se;
        int l=0,ans=0;
        for(int r=0;r<s.size();++r){
            if(!se.count(s[r])) se.insert(s[r]);
            else{
                while(l<s.size()&&s[l]!=s[r]){
                    se.erase(s[l]);
                    ++l;
                }
                ++l;
            }
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};

func lengthOfLongestSubstring(s string) int {
    ma:=make(map[uint8]struct{})//无序set存储字符
    l,r,ans:=0,0,0//l,r滑动窗口左右边界,ans记录答案
    for ;r<len(s);r++{
        if _,ok:=ma[s[r]];!ok{
            ma[s[r]]=struct{}{}
        }else{
            for l<r&&r<len(s)&&s[l]!=s[r]{
                delete(ma,s[l])
                l++
            }
            l++
        }
        ans=max(ans,r-l+1)
    }
    return ans
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}