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

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

方法一:暴力哈希表

由于c++的字符可通过ASCII转化为0-127直接的整数,可以先创建一个长度为128的数组scan作为哈希表,之后开始扫描所给的字符串s:指针不动,指针开始扫描,扫描完成后即为子串长度:

  • 如果该字符在哈希表scan中不存在,即scan[s[j]] == 0,就将scan[s[j]]加一,继续扫描下一个字符,即scan[s[j++]]++;。然后更新当前最长子串的长度ans为j-i与之前的ans这两者中的最大值
  • 如果该字符在哈希表scan中已经存在,即scan[s[j]] == 1,就说明当前子串已经出现重复字符,该轮扫描结束,令i加一继续下一轮扫描
int lengthOfLongestSubstring1(string s)
{
    int ans = 0;

    for(int i = 0; i < s.length(); i++)
    {
        int j = i;
        vector<int> scan(128);
        while(j < s.length() && scan[s[j]] == 0)
        {
            scan[s[j++]]++;
            ans = max(ans, j-i);
        }
    }
    return ans;
}

方法二:滑动窗口

创建一个长度为128(ASCII中的字符数)的vector作为哈希表并将其全部初始化为-1(无效下标),使用快慢指针扫描字符串:快慢指针同时指向字符串首,快指针一直遍历,慢指针根据特殊规则移动:

  • 如果当前快指针指向的字符第一次出现,就将哈希表中该字符所在的位置重置为当前字符在字符串中的下标,快指针指向下一个字符
  • 如果当前快指针指向的字符已经出现过一次,就通过哈希表将慢指针重指向该字符上一次出现的位置的下一个位置,快指针指向下一个字符
  • 在以上两个分支结束后均需要通过快指针和慢指针的相对位置来更新所求的最大字串长度
int lengthOfLongestSubstring(string s)
{
    int ans = 0;
    int fast = 0, slow = 0;
    vector<int> Hash_Map(128,-1);

    for(; fast < s.length(); fast++)
    {
        char temp = s[fast];      
        if(Hash_Map[temp] >=slow) 
            slow = Hash_Map[temp] + 1;

        Hash_Map[temp] = fast;
        ans = max(ans, fast - slow + 1);             
    }
    return ans;
}


本文章使用limfx的vscode插件快速发布