字符串最长不含重复字符的子串长度

红太狼 2022-10-14 14:56 213阅读 0赞

题目很简单，假如输入“abcdbf”，那么最长不含重复字符的字串就为“cdbf”，长度就是4.这里没有要求输出子串，想要输出稍微加点东西就行了。从网上看了很多个版本，一般用的是动态规划。但是这个算法不需要用到动态规划。从网上搜到一个很好的代码，共享之。这个算法很容易理解。

首先定义一个hash表，也就是times这个表。记录每个字符是否出现过，要是没有出现就是0，出现了就把它置为1.要是没有遇到重复的，就把end指针一直后移，同时最大的长度也要增加。要是遇到重复的了。假如abcdb，这时候遇到第二个b了，我就从头开始，一直找到第一个b，把这之间的次数都重新置为0.这样b被置为0后，第一个if语句才能得以继续执行。不知道我这样解释清楚了没有，实在佩服作者这种简洁直观的代码。

#include <iostream>
    using namespace std;
    
    #define CHAR_SET_SIZE 256
    
    int GetMaxUSubStrLen(char *s)
    {
    	int maxLen = 0;
    	int times[CHAR_SET_SIZE] = {0};
    	char *pStart, *pEnd;
    
    	pStart = pEnd = s;
    	while (*pEnd != '\0')
    	{
    		int idx = (*pEnd);
    		if (times[idx] == 0)
    		{
    			++pEnd;
    			times[idx] = 1;
    			if (pEnd - pStart > maxLen)
    				maxLen = pEnd - pStart;
    		}
    		else
    		{
    			int idx_s = (*pStart);
    			times[idx_s] = 0;
    			++pStart;
    		}
    	}
    
    	return maxLen;
    }
    int main()
    {   
    
      char a[]= "abcbef";
      cout<<GetMaxUSubStrLen(a)<<endl;
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关最长无重复子串长度

[题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。][s _ _] > 解题思路：滑动窗口/双指针（计算长度） + hashMap（判重）

雨点打透心脏的1/2处/ 2024年03月08日 08:18/ 0 赞/ 98 阅读

相关最长不含重复字符串的子字符串

一、题目描述请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含′a′′a′~′z′′z′的字符。例如，在字符串"arabcac

落日映苍穹つ/ 2024年02月19日 19:27/ 0 赞/ 56 阅读

相关最长不含重复字符串的子串

一、题目从字符串中找到一个最长的不包含重复字符串的子字符串，计算该子字符串的长度二、分析动态规划 f(i)表示以第i个字符为结尾的不包含重复字符的子串的最长长度，

悠悠/ 2023年11月28日 06:00/ 0 赞/ 250 阅读

相关 java 最长不重复子串,最长无重复字符子串

正文在下面，先打个广告： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

谁借莪１个温暖的怀抱￠/ 2022年12月24日 15:59/ 0 赞/ 204 阅读

相关最长不含重复字符的子字符串

最长不含重复字符的子字符串 1、参考资料 https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi

深藏阁楼爱情的钟/ 2022年12月05日 05:24/ 0 赞/ 184 阅读

相关 54：最长不含重复字符的子字符串

最长不含重复字符的子字符串 public class Offer54 { public static void main(String[] ar

川长思鸟来/ 2022年11月29日 11:26/ 0 赞/ 178 阅读

相关【字符串】最长不含重复字符的子字符串

1. 题目描述题目链接：[最长不含重复字符的子字符串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

水深无声/ 2022年11月26日 07:59/ 0 赞/ 182 阅读

相关字符串最长不含重复字符的子串长度

题目很简单，假如输入“abcdbf”，那么最长不含重复字符的字串就为“cdbf”，长度就是4.这里没有要求输出子串，想要输出稍微加点东西就行了。从网上看了很多个版本，一般用的是

红太狼/ 2022年10月14日 14:56/ 0 赞/ 214 阅读

相关找到字符串的最长无重复字符子串

【题目】给定一个字符串str，返回str的最长无重复字符子串的长度。【举例】 str="abcd"，返回4 str="aabcb"，最长无重复字符子串为"a

妖狐艹你老母/ 2022年07月15日 14:43/ 0 赞/ 238 阅读

相关最长重复子串和最长不重复子串求解

1最长重复子串 1.1问题描述首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次，则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重

布满荆棘的人生/ 2022年07月13日 02:21/ 0 赞/ 214 阅读