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

题目

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

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

解题思路

本道题目考察的知识点：

1. 对特殊情况的处理；
2. 利用hash表判断字符是否重复；

伪代码

lengthOfLongestSubstring
{
  长度为1直接返回;
  去除字符串头部的重复字符;
  index和pre_index指向第一个元素;
  while (index < (length - max_len) && pre_index < length)
  {
    if (hash[string[pre_index]] == 0)
    {
      hash[string[pre_index]] = 1;
      pre_index++;
      记录子字符串最大长度max_len;
    }
    else
    {
      hash[string[pre_index]] = 0;
      index++;
    }
  }
  
  return max_len;
}

解答

int lengthOfLongestSubstring(char* s) {
  int max_len = 0;
  int index = 0, pre_index = 0;
  char hash[256] = {0};
    
  const char* pString = s;
  int length = strlen(s);
    
  /* 空指针保护 */
  if (!pString) 
    return 0;

  /* 长度为1数组的特殊处理 */
  if (length == 1)
    return 1;

  /* 对数组最前面的重复字符的剔除，例如bbbcfg截断成bcfg */
  for (; index < length - 1; index++) 
  {
    if (pString[index] != pString[index+1]) 
      break;
  }
  pString = pString + index;
  length = strlen(pString);
  /* 长度为1数组的特殊处理 */
  if (length == 1)
    return 1;
    
  /* 对新数组从0开始处理 */
  index = 0;
  memset(hash, 0, sizeof(hash));
    
  while (index < (length - max_len) && pre_index < length) 
  {
    /* hash表的位置对应字符，内容对应该字符是否出现 */
    if (hash[pString[pre_index]] == 0) 
    {
      hash[pString[pre_index]] = 1;
      pre_index++;
      max_len = (max_len < (pre_index - index)) ? (pre_index - index) : max_len;
    }
    else
    {
      hash[pString[index]] = 0;
      index++;
    }
  }
 
  return max_len;
}