3. Longest Substring Without Repeating Characters 无重复字符的最长子串

本文主要是介绍3. Longest Substring Without Repeating Characters 无重复字符的最长子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目大意:给一个字符串,要求出最长的不含重复字符子串(要求连续,不是子序列).
解题思路:不重复,利用哈希表.hash是以字符的ASC为下标的数组,对应存储该字符最后出现的位置.
设一个标记start,然后一次遍历,更新每个字符在哈希表中的最新位置,以及最大长度.关键在于start的更新,对字符i,dict[s[i]]为i在串s中上一次出现的位置,若该位置大于当前start,则用该位置更新start.因为要求的事不含重复子串长度,因此用i的新旧位置之差i-start来求.
代码:

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> dict(256, -1);  //字符哈希表int start = -1, maxLen = 0;for (int i = 0; i < s.length(); i++) {if (dict[s[i]] > start) {start = dict[s[i]];  //关键}dict[s[i]] = i;maxLen = max(maxLen, i - start);}return maxLen;}
};

python:

class Solution:def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""dict = [-1] * 256start = -1maxLen = 0for i, val in enumerate(s):if dict[ord(val)] > start:  #注意asc码与整数需要转换，不像c++那样便捷start = dict[ord(val)]dict[ord(val)] = imaxLen = max(maxLen, i - start)return maxLen

这篇关于3. Longest Substring Without Repeating Characters 无重复字符的最长子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---