大数据中如何实现无重复字符的最长子串算法

2023-06-19 11:06:32 572人浏览安东尼

摘要

这篇文章给大家分享的是有关大数据中如何实现无重复字符的最长子串算法的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。无重复字符的最长子串 &nbs

这篇文章给大家分享的是有关大数据中如何实现无重复字符的最长子串算法的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

无重复字符的最长子串

大数据中如何实现无重复字符的最长子串算法

思路答案

首先定义一个指针p指向该字符串的链头，然后通过p指针后的第i个字符是否和p指针后的第j个字符相同来取得最大长度。（也叫做完全遍历）

但是面临一个问题，如果一个字符串特别大，全都遍历一遍，时间复杂度为O（n^3），这样一看，虽然能解决问题，但是实在是太慢了，算法如果没有效率，就没有太大的意义。

所以采取了已下措施：

举个例子说明以下这个措施，字符串s为："dabcabcbb"，当执行到j =4、i=1时，也就是j指向第二个“a”，i指向第一个“a”的时候。这时候，按照之前的遍历方式，p指针应该+1就ok，但是如果+1的话，abca是刚才dabca的子集，所以没有必要判断这一步，即可以省略这一步！所以进行了以下优化：

完全遍历：

p = p + 1;

改进之后：

p = p + i + 1;

完整代码如下：

int lengthOfLongestSubstring(char* s) {
 char* p = s;
  int i = 0, j = 0, len = 0;
  for(j = 0; *(p+j) != '\0'; j++){
    for(i = 0; i < j; i++){
      if(*(p+i) == *(p+j)){
        p = p + i + 1;
        if(j > len) len = j;
        j = 0;
        break;
      }
    }
  }
  len = (j > len )? j : len;
  return len;
}

感谢各位的阅读！关于“大数据中如何实现无重复字符的最长子串算法”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 大数据中如何实现无重复字符的最长子串算法

本文链接: https://www.lsjlt.com/news/295806.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341