Leetcode 3. 无重复字符的最长子串

  • 时间:
  • 来源:互联网
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Fire_to_cheat_/article/details/103353647

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 1:

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

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:

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

思路:
采用一个数组记录所有字母的下标位置,利用滑动窗口的思想,入到窗口中有两个相同的字母时,将窗口开始节点更新到重复字母的后一个位置。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>vec(128,-1);
        int i(0),j(0),result(0);
        int len=s.length();
        if(len==0)return 0;
        if(len==1)return 1;
        int length=0;
        while(i<len&&j<len)
        {
            char tmpchar=s[j];
            if(vec[int(tmpchar)]>=i)
            {
                i=vec[int(tmpchar)]+1;
            }
            vec[int(tmpchar)]=j;
            j++;
            result=max(result,j-i);
            
        }
        return result;

    }
};

本文链接http://element-ui.cn/news/show-502.aspx