LeetCode攀登之旅(2)

2019 年 10 月 5 日
筆記

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.作者的话

最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！更多刷题，请关注本公众号算法系列！