2021秋招-算法-哈希算法-哈希表

LeetCoe-03-无重复字符的最长字串

LeetCode链接:LeetCoe-03-无重复字符的最长字串

题目理解及描述

3. 无重复字符的最长子串难度中等3747给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: “abcabcbb”
   输出: 3
   解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
   示例 2:输入: “bbbbb”
   输出: 1
   解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
   示例 3:输入: “pwwkew”
   输出: 3
   解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
   请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

思路:

1. 暴力方法: 时间: O(N**2) 空间: O(N)
   seq_lengths = []
   for i, token in enumerate(s):

# 遍历每个字符

for j in range(i:len(s):
	# 对于每个开始字符计算其下一次重复或者不重复的最长字串
	j += 1
	seq_len = j - i

	if s[i] == s[j]:
		break
	seq_lengths.aapend(seq_len)
1
2
3
4
5
6
7
8
9
10

return max(seq_lengths)
4. 进一步优化: 内部第二个循环每次从当前位置向后寻找最长无重复字符串, 可以使用 hasMap{}来存储每个字符在字符串中的位置，如果遇到重复就进行更新;

思想: 一般方法都是从当前字符往后找,然后找到一个重复的字符停止; 可使用双指针的思路: 左指针指向当前字符, 右指针指向往后找的指针; 
自己还没有真正理解清楚这道题; 如果暴力做: 1.当前字符  2. 向后查找  3.判断重复; 


class Solution():
	# 方法1: 
	def lengthOfLongestSubstring(self, s:str):
		hasMap = {}	
		res = 0		# result
		p = -1		# 哑节点  记录计算当前最长字符串的起始位置
		for i, token in enumerate(s):
			if token in hasMap and hasMap[token] > p:
				p = hasMap[token]  # 起始位置进行更新 
				hasMap[token] = i
			else:		
				hasMap[token] = i
				res = max(res, p-i)
		return res
    	
    	# 方法2: 类似于双指针进一步优化hasMap()
	def lengthOfLongestSubstring(self, s: str) -> int:
	        s = list(s)
	        hashmap = {}
	        start, end = 0,0
	        maxlen = 0
	        for i,j in enumerate(s):
	            if j in hashmap:
	            	# 这一步自己做肯定会忘记
	                if start>hashmap[j]:
	                    hashmap[j] = i
	                else:
	                    start = hashmap[j] + 1
	            end += 1
	            hashmap[j] = i
	            maxlen = max([maxlen, end-start])
	        return maxlen   
	      
 # 方法3: 代码进一步整理
 def lengthOfLongestSubstring(self, s: str) -> int:
         s = list(s)
         hashmap = {}
         start, end = 0,0
         maxlen = 0
         for i,j in enumerate(s):
             if j in hashmap:
              # 这一步自己做肯定会忘记
                 if start <= hashmap[j]:
                     start = hashmap[j] + 1
             end += 1
             hashmap[j] = i
             maxlen = max([maxlen, end-start])
         return maxlen   
 
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

进一步想法: