LeetCode--最长不含重复字符的子字符串

LeetCode--最长不含重复字符的子字符串

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

说明

leetcode题，面试48

最长不含重复字符的子字符串

题目

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

Go语言

思路

遍历字符串，使用map记录重复元素出现的位置，对比子串的长度，发现最长的及时更新

代码

func lengthOfLongestSubstring(s string) int {
    //创建一个map集合
    lastOccured := make(map[byte]int)
    //计数器
    startI := 0
    //长度
    maxLength := 0

    //遍历string
    for i, ch := range []byte(s) {
        //判断集合不为空
        if lastI, ok := lastOccured[ch]; ok && lastI >= startI {
            startI = lastI + 1
        }
        //计算最长的子串
        if i-startI+1 > maxLength {
            maxLength = i - startI + 1
        }
        //记录最后一次出现的位置
        lastOccured[ch] = i
    }
    return maxLength
}

Python语言

思路一（滑动窗口）

• 初始化头尾指针 head，tail；

• tail 指针右移，判断 tail 指向的元素是否在 [head:tail] 的窗口内；

  • 如果窗口中没有该元素，则将该元素加入窗口，同时更新窗口长度最大值，tail 指针继续右移；

  • 如果窗口中存在该元素，则将 head 指针右移，直到窗口中不包含该元素。

• 返回窗口长度的最大值。

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        head = 0
        tail = 0
        # 判断是否为边界
        if len(s) < 2:
            return len(s)
        # 两个指针停留在第一个元素的位置，初始长度为1
        res = 1
        while tail < len(s) - 1:
            tail += 1
            if s[tail] not in s[head:tail]:
                res = max(tail-head + 1,res)
            else:
                while s[tail] in s[head:tail]:
                    head += 1
        return res

思路二（哈希表）

• tail 指针向末尾方向移动；
• 如果尾指针指向的元素存在于哈希表中：
  • head 指针跳跃到重复字符的左边一位；
• 更新哈希表和窗口长度。

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        hashmap = {}
        head,res = 0,0
        for tail in range(n):
            # 如果说尾指针存在哈希表中，把头指针跳转到开始重复元素的上一位
            if s[tail] in hashmap:
                head = max(hashmap[s[tail]],head)
            # 更新哈希表
            hashmap[s[tail]] = tail +1
            # 更新长度
            res = max(res,tail-head+1)
        return res

C++

• r 指针向末尾方向移动；
• 如果尾指针指向的元素存在于哈希表中：
  • l 指针跳跃到重复字符的左边一位；
• 更新哈希表和窗口长度（时刻返回最大的值）。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> m;
        int ret = 0,l = 0, r=0;
        while(r<s.size()){
            //判断边界
            if(m.find(s[r]) != m.end()){
                l = max(l,m[s[r]]+1);
            }
            m[s[r++]] = r;
            ret = max(r-l,ret);
        }
        return ret;
    }
};

C语言

思路

滑动窗口

代码

int lengthOfLongestSubstring(char* s){
    int count[95]; // ASCII中存在95个可打印的字符，记录遍历s时遇到的字符
    memset(count, 0, 95 * sizeof(int)); // 将count的值全部置为0
    int max_lenght = 0; // 不含重复字符的子字符串的最大长度
    int temp = 0; // 存储遍历s时所寻找到的不含重复字符的子字符串的长度
    int p1 = 0, p2 = 0;
    while(s[p1] != '\0' && s[p2] != '\0'){

        if(count[s[p2] - ' '] == 0){ // 没有遇到重复字符
            count[s[p2] - ' '] = 1; // 记录遇到的字符
            p2 += 1;
            temp = p2 - p1;
        }
        else{ // 遇到重复字符
            temp = p2 - p1;
            count[s[p1] - ' '] = 0; // 删除对p1位置字符的记录
            p1 += 1; // p1右移
        }

        if(temp > max_lenght){
            max_lenght = temp;
        }
    }
    return max_lenght;
}

感谢

leetcode

以及勤劳的自己