LeetCode攀登之旅(2)
LeetCode攀登之旅(2)
LeetCode攀登之旅(2)
0.本节思想
1.两数之和
2.无重复字符的最长子串
3.作者的话
0.本节思想
数据结构：哈希表 形式：(key,value)
1.两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]暴力解决本题就是双重for循环，此法效率太低，这里采用O(n)的时间复杂度算法，哈希思想算法。
首先给定nums=[2,7,11,15],利用这个数组去构造key，value。
nums[i]即为里面的value,key即为index。
那如果换成nums[i]为value,key为index呢，如果采用这个方法，在去遍历的时候，很不方便，因为我们是直接找对应的差值是否在这个哈希表中，如果nums[i]换成了value，则直接查找不到了！
以下给出Python实现代码：
- 新建一个hash表
- 通过enumerate循环可以直接获取key与value
- 然后根据key得到其中一个数，再根据此数从哈希表中寻找另外一个数
- 一开始哈希表为空，另外一个数肯定不存在哈希表中，那么我们每次给哈希表赋值，key为number,value为index
- 最终返回的两个数的顺序为哈希表中的index与当前遍历的index。或者直接sorted排序即可！
【哈希code】
class Solution:
def twoSum(self,nums,target):
nums_hash = {}
for index,number in enumerate(nums):
one_num = nums[index]
other_num = target-one_num
if other_num in nums_hash:
return [nums_hash[other_num],index]
nums_hash[number] = index
return []手动推演：
nums = [2,6,8,9] target=10
当one_num = 2(index=0)时,other_num=8,此时这个数不在哈希表中，先将当前数加入哈希表中，得到nums_hash = {2:0}
当one_num=6(index=1)时候，other_num=4，继续重复上述操作，得到nums_hash={2:0,6:1}
当one_num=8(index=2)时，other_num=2，此时此数在哈希表中，直接返回[nums_hash[other_num],index] ，循环结束，退出程序。
2.无重复字符的最长子串
给定一个字符串，找出不含有重复字符的最长子串的长度。 示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。暴力解法： 【解题思想】 首先想到遍历整个字符，然后对遍历到的每个字符后的字符处理，即判断它是否是重复元素，这个判别可以通过list/dict/str解决，如果检查的字符不在这个判别list/dict/str里面，则加入进去，并记录本次长度，在最外面定义一个最大长度标记，将每次的长度与最大长度对比，取最大即为最终结果！ 【暴力code】
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
MaxLength = 0
for i in range(len(s)):
st = ''
count = 0
for j in s[i:]:
if j not in st:
st += j
count += 1
if (MaxLength<count):
MaxLength=count
else:
break
return MaxLength手动推演：
给定字符s="pwwkew"，首先得到s的总长6，接着对其做6次循环。
当i=0时：count=0，此时的j的范围为"pwwkew"
内部过程如下：
st='p' count=1 MaxLength=1 st='pw' count=2 MaxLength=2
w in st中，直接退出本次循环
跳至外部循环如下：
当i=1时：count=0，此时的j的范围为"wwkew"
内部过程如下：
st='w' count=1 MaxLength=1
w in st中，直接退出本次循环
跳至外部循环如下：
当i=2时：count=0，此时的j的范围为"wkew"
内部过程如下：
st='w' count=1 MaxLength=2 st='wk' count=2 MaxLength=2
st='wke' count=3 MaxLength=3
w in st中，直接退出本次循环
跳至外部循环如下：
当i=3、4、5，依此重复上述过程，最终返回MaxLength哈希解法： 注意到上述的手动推演了？可以看到在下次查找重复元素时，实际上白做了这么一段过程，比如：i=0可直接跳到i=2情况下，那么此时效率肯定会高很多，也就是当i=1时是没有用的，因为去掉一个元素后，不可能比之前的元素长度还长！ 以下分别为i=0,i=1,i=2的情况
p w w k e w
i
j
hash_str = pw p w w k e w
i
j
hash_str = w p w w k e w
i
j
hash_str = w 【解题思想】 于是乎新思想出来了，我们跳过i=1的过程，直接从两个相等情况入手，而存储的j位字符为上述的哈希表，没错，我们仿照上述两数之和的哈希思想去解决这个问题，会变得非常简单，从原先的O(n^2)变为现在的O(n)复杂度！ 这里有一点注意，最大长度是根据index与start位置变化，所以这里是index-start+1
实质：例如：字符串为"pswkwabc"，原先按照暴力解法，直接循环每一个元素，
那么用哈希跟跳过重复元素解决则为，从
p s w k w a b c
start
直接指向了重复元素w的后一个元素k，刚好跳过重复元素
p s w k w a b c
start【哈希code】 看下面代码跟上述两数之和，及其相似，一个是找到元素就退出，一个是等对比完，找出最大长度，才退出！
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = MaxLength = 0
hash_str = {}
for index,char in enumerate(s):
if char in hash_str and start<=hash_str[char]:
start = hash_str[char]+1
else:
if(MaxLength<(index-start+1)):
MaxLength=index-start+1
hash_str[char] = index
return MaxLength手动推演： 以pwwkew为例:
-------------------------
start = MaxLength = 0 hash_str = {}
index = 0, char= 'p' 此时char不在hash_str中，进入else里面
MaxLength=1 退出判断， hash_str={'p':0}
-------------------------
index = 1, char= 'w' 此时char不在hash_str中，进入else里面
MaxLength=2 退出判断， hash_str={'p':0,'w':1}
-------------------------
index = 2, char= 'w' 此时char在hash_str中，并且start=0<hash_str['w']=1，进入if里面
start=2 退出判断， hash_str={'p':0,'w':1,'w':2}
-------------------------
index = 3, char= 'k' 此时char不在hash_str中，进入else里面
MaxLength=2 退出判断， hash_str={'p':0,'w':1,'w':2,'k':3}
-------------------------
index = 4, char= 'e' 此时char不在hash_str中，进入else里面
MaxLength=3 退出判断， hash_str={'p':0,'w':1,'w':2,'k':3}
-------------------------
index = 4, char= 'e' 此时char在hash_str中，并且start=2=hash_str['w']=2，进入if里面
start=3 退出判断， hash_str={'p':0,'w':1,'w':2,'k':3，'w':4}
-------------------------
return MaxLength=3【效率对比】
暴力解法图
哈希解法图
3.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多刷题，请关注本公众号算法系列！