LeetCode 3——无重复字符的最长子串

Rocture 发布于2019-07-31 11:16 / 1236人阅读

摘要：题目解答方法一我们从前往后遍历字符串，代表最长子串的起始位置，一开始设置为零。如果没有遇到重复字符，则更新子串的长度，向后遍历。最长子串的起始位置重复的字符在子串中的位置初始化映射自动初始化为零获取更多精彩，请关注

1. 题目

2. 解答 2.1. 方法一

我们从前往后遍历字符串，start 代表最长子串的起始位置，一开始设置为零。

如果没有遇到重复字符，则更新子串的长度，向后遍历。

如果遇到重复字符时，则更新字符串起始位置为上一个相同字符的后面一个位置，同时更新子串长度。

重复上面这个过程，直到遍历完毕。

"abcabc"，start = 0，str_len = 1, 2, 3
此时第二次遇到 "a"，start = 1，str_len = 3
此时第二次遇到 "b"，start = 2，str_len = 3
此时第二次遇到 "c"，start = 3，str_len = 3

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        max_len = 0
        str_len = 0
        start = 0      # 最长子串的起始位置
        index = 0     # 上一个相同字符在子串中的位置，是一个相对位置，不是在原字符串中的位置
        
        for i in range(len(s)):
            
            if (s[i] not in s[start:i]):
                str_len += 1
               
            # 如果遇到重复字符，更新子串的起始位置为上一个相同字符的后面一个位置
            # 同时我们需要更新子串长度
            else:
                max_len = max(max_len, str_len)
                index = s[start:i].find(s[i])
                str_len = str_len - index
                start = start + index + 1 
                
        max_len = max(max_len, str_len) # 一直没有遇到重复字符
        return max_len

2.2. 方法二

方法一中，我们每次判断当前字符是否为重复字符时，都需要在子串中进行搜索，更新子串起始位置时，也要在子串中搜索上一个相同字符的位置，效率很低。

其实我们需要知道的就是一个子串的起始位置，然后往后遍历的时候只需要在适当的时候更新这个起始位置重新计算子串长度即可。

因此，我们可以建立一个当前字符和当前字符下一个位置的映射。

所有映射全部初始化为零，start = 0。从前往后开始遍历字符串，同时更新映射，计算子串长度。

如果当前字符的映射大于 start，说明在 satrt 后面出现过当前字符，就更新 start。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0
        str_len = 0
        start = 0    # 最长子串的起始位置
        index = 0   # 重复的字符在子串中的位置
        
        # 初始化映射
        table = []
        for i in range(128):
            table.append(0)
                
        for i in range(len(s)):
            
            start =  max(start, table[ord(s[i])])

            str_len = i - start + 1    
            max_len = max(max_len, str_len)
            
            table[ord(s[i])] = i + 1
            
        return max_len

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int table[128] = {0}; // 自动初始化为零
        int max_len = 0;
        int str_len = 0;
        int start = 0;
        
        string::iterator it = s.begin();
            
        for (int j = 0; it != s.end(); it++, j++)
        {
            start = start > table[*it] ? start : table[*it];
            table[*it] = j + 1;
            str_len = j - start + 1;
            max_len = max_len < str_len ? str_len : max_len;
        }
        
        return max_len;
    }
};

获取更多精彩，请关注「seniusen」!

云服务器 GPU云服务器最长公共子串 java最长相同子串字符串找子串算法字符串最大子串c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44912.html

LeetCode3.无重复字符的最长子串JavaScript

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。 LeetCode3.无重复字符的最长子串JavaScript 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2: 输入: bbbbb输出...

vboy1010 2019-08-23 14:46 评论0 收藏0
【leetcode】3. 无重复字符的最长子串

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。完成循环后取队列中出现的最大长度即可。给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2：输入: bbbbb 输出: 1 解释:...

qc1iu 2019-08-23 18:32 评论0 收藏0
LeetCode.3 无重复字符的最长子串(JS)

摘要：先跳到第三题是因为第二题第一眼没读懂一题目无重复字符的最长子串给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例输入输出解释因为无重复字符的最长子串是，所以其长度为。以此来实现判断是否包含重复字符。先跳到第三题是因为第二题第一眼没读懂一、题目无重复字符的最长子串：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例1 输入: abcabcbb输...

wthee 2019-08-23 16:18 评论0 收藏0
leetcode 无重复字符的最大子串

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。临时存储子串存储最长子串如果子串中不存在如果子串中存在重复字符的位置截取字符串给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2...

laoLiueizo 2019-08-23 13:49 评论0 收藏0
力扣(LeetCode)3

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。若没有重复元素，则区间右边扩大，否则区间左边缩小。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符...

_DangJin 2019-08-16 15:43 评论0 收藏0