【LeetCode刷题记录】3. 无重复字符的最长子串

题目描述:
【LeetCode刷题记录】3. 无重复字符的最长子串
题解:
一、暴力破解(时间复杂度:O(n3),空间复杂度:O(min(n,m)),超出时间限制(TLE))
BF方法的思路比较简单,逐个检查所有的子字符串,看它是否不含有重复的字符。取不重复子字符串中长度最大的那个作为结果输出。
二、双指针滑动窗口(时间复杂度:O(n2),空间复杂度:O(1))

int lengthOfLongestSubstringSlide(string s) {
 int i = 0, j = 0, len = 0, rst = 0;
 while (j < s.size()) {
  char c = s[j];
  for (int idx = i; idx < j; idx++) {
   if (c == s[idx]) {
    i = idx + 1;
    len = j - i;
    break;
   }
  }
  j++;
  len++;
  rst = rst > len ? rst : len;
 }
 return rst;
}

思路:每次检查后指针指向的字符是否在前指针到后指针之间出现过,未出现,则后指针后移,长度+1,检查、更新结果;出现,则前指针移至出现位置的下一位置,更新长度值,后指针后移,长度+1,检查、更新结果。
三、哈希表优化方法二(时间复杂度:O(n),空间复杂度:O(n))

int lengthOfLongestSubstringSlideHash(string s) {
 int i = 0, j = 0, len = 0, rst = 0;
 unordered_map<char, int> record;
 while (j < s.size()) {
  char c = s[j];
  if (record.find(c) != record.end() && record[c] >= i)
  {
   i = record[c] + 1;
   len = j - i;
  }
  record[c] = j;
  j++;
  len++;
  rst = rst > len ? rst : len;
 }
 return rst;
}

使用哈希表,用空间换时间。
关于哈希表,参考:C++: map/hash_map/unordered_map

上一篇:C#字符串表达式的动态编译及执行


下一篇:异步复位和同步释放电路的详细解释