求字符串中的最长不重复子串

题目描述：

给定一字符串只包含数字，请写一个算法，找出该字符串中的最长不重复子串（不重复是指子串中每一元素不同于子串中其他元素）
如：“120135435”最长不重复子串为 “201354”

实现如下：

//时间复杂度O(n)
//空间复杂度O(m)
class Solution
{
public:int maxNum(int num1, int num2){return num1 >= num2 ? num1 : num2;}void maxNonRepetitiveString(string str){if (str.empty())return;//map整形数组一共有10个元素，用来保存0-9数字的最后一次出现的下标int map[10];//将map数组的所有元素初始化为-1for (int i = 0; i < 10; ++i)map[i] = -1;int begin = 0; //begin用来记录最长无重复子串的起始下标int end = 0; //end用来记录最长无重复子串的终止下标int current = 0; //current用来记录当前得到的无重复子串长度int pre = -1; //pre用来记录当前无重复子串的起始位置-1int len = 0; //len用来记录最长无重复子串的长度for (int j = 0; j < str.length(); ++j){//判断pre在当前字符最后一次出现位置的左边还是右边//如果在左边，即pre//如果在右边，即pre>=map[str[j]]，表示在str[j]的位置没有出现重复字符pre = maxNum(pre, map[str[j]]);//计算当前无重复子串的长度current = j - pre;//比较当前无重复子串长度是否大于最大无重复子串长度if (len <= current){begin = pre + 1; //更新无重复子串的起始下标end = j; //更新无重复子串的终止下标}len = maxNum(len, current); //更新最长无重复子串的长度map[str[j]] = j; //更新str[j]字符最后一次出现的位置下标}//打印最长无重复子串for (int k = begin; k <= end; ++k)cout << str[k];}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！