LeetCode_哈希算法应用 -快捷查找

忘是亡心i 2023-07-02 16:22 23阅读 0赞

声明：以下所有题都借鉴所有大佬们整合而成，我只是做了一下笔记，若有违法侵权，还望及时告知进行删除处理。

### 文章目录 ###

*  题目1 两数之和
 *   *  题解1 暴力题解(面试的时候千万不要回答这个)
     *  题解2 类哈希表, temp.index索引
     *  题解3 哈希表
     *   *   *   *  哈希直接建立版
 *  题目2 三数之和
 *   *  去重详解
     *   *   *  思考:为何使用哈希表去重，而不是直接如下所示:\*\*
     *  题解1 暴力题解
     *  题解2 指针图解
     *   *  值得学习之处:
     *  题解3 哈希表
     *   *  值得学习之处
 *  题目4 四数之和 利用哈希解锁
 *  总结:

# 题目1 两数之和 #

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。  
**例如:**  
给定 nums = \[2, 7, 11, 15\], target = 9  
因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

## 题解1 暴力题解(面试的时候千万不要回答这个) ##

# 伪代码
    for i 
    	for j
    		if i+j = target

## 题解2 类哈希表, temp.index索引 ##

''' 解释:表相当与一个三角形 temp 第一次搜索1次 第二次搜索2次 直到搜素到结果,也就是时间复杂度O(N^2),这比哈希表多出来的N就是每次遍历搜索造成的 '''
    class Solution(object):
        def twoSum(self, nums, target):
            j=-1
            for i in range(1,len(nums)):
                temp = nums[:i]  # 目标值一定在temp中, 因为查找一个放进去
                nums_second = target - nums[i]
                if nums_second in temp:
                    j = temp.index(nums_second )
                    break
            if j>=0:
                return [j,i]
            else: return []
    
    def  main():
        print(Solution().twoSum([2, 7, 11, 15], 9))
        pass
    
    if __name__ == '__main__':
        main()

![在这里插入图片描述][20200131120649921.png]

# 改进版
    '''仔细一想,其实跟哈希表很像,在改进就是哈希表了,if (target - num) in temp:'''
    class Solution(object):
        def twoSum(self, nums, target):
            temp = [nums[0],]
            for i,num in enumerate(nums[1:]):
                if (target - num) in temp:
                    j = temp.index(target - num)
                    return [j,i+1]
                else: temp.append(num)
            return []

![在这里插入图片描述][20200131121746695.png]

## 题解3 哈希表 ##

# 时间复杂度:O(n)
    ''' 解析: 一次遍历, 如果差值不在哈希表中,将当前值放入哈希表,直到遇到第二个值与第一个值匹配, 直接从哈希表中索引到结果 '''
    class Solution:
        def twoSum(self, nums, target):
            hashmap={ }
            for i, num_1 in enumerate(nums):
                num_2 = target - num_1
                if num_2 in hashmap:
                    return [hashmap[num_2], i]
                hashmap[num_1]=i
            return None

![在这里插入图片描述][20200131165856242.png]

##### 哈希直接建立版 #####

因为需要查找,那为何不直接先将待查找数据建立哈希表.然后我发现建立完哈希表后查找速度,比每一次向哈希表插入数据速度更快,因为插入也需要时间

class Solution:
        def twoSum(self, nums, target):
            hashmap_another = { target-num : i for i,num in enumerate(nums)}
            print(hashmap_another)  
            for i,num in enumerate(nums):  
                if num in hashmap_another:
                    if i != hashmap_another[num]:
                        return [i,hashmap_another[num]]
            return []

![在这里插入图片描述][20200131164814421.png]

# 题目2 三数之和 #

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。  
**例如：给定 输入 \[-1, 0, 1, 2, -1, -4\]，输出\[\[-1,-1,2\],\[-1,0,1\]\]**

## 去重详解 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">去重有两部分</th> 
   <th align="center">解决方案</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">输入中重复的数据</td> 
   <td align="center">先排序后遍历遇到重复continue</td> 
  </tr> 
  <tr> 
   <td align="center">结果中重复的数据</td> 
   <td align="center">建立哈希表 key为str[i.v, j.v, k.v]，value为True</td> 
  </tr> 
 </tbody> 
</table>

#### 思考:为何使用哈希表去重，而不是直接如下所示:\*\* ####

# 直接去重
    if res_ not in res:
    	res.append(res_)

# 哈希表 结果去重
    hashmap = { }
    res_ = sorted([i.v, j.v, k.v]) # [-1, -1, 2] 
    key = ','.join([str(x) for x in res_]) # "-1,-1,2"
    if key not in hashmap:
    	hashmap[key] = True  # hashmap{"-1,-1,2":True}
    	res.append(res_)

## 题解1 暴力题解 ##

# 时间复杂度O（N^3）
    # 伪代码
    for i in nums: # 0,1,2,3,4...
        for j in nums[i+1:]: # 1,2,3...
            for k in nums[j+1]: # 2,3,4...
                if nums[i]+nums[j]+nums[k] == 0:
                    if 不重
                    res.append([i,j,k])

## 题解2 指针图解 ##

### 值得学习之处: ###

1.  类似快排,分而治之
2.  循环去重,`i+=1; while(nums[i] == nums[i-1]) continue;`不会超出索引范围还能去除重复得到目标索引
3.  不需要结果去重,因为循环去重已经间接解决结果去重
4.  细节:判定sum为0时,  
    可以`if sum>0 elif sum<0 else`,便对比程序中少了一个判断的时间
5.  pass

![图解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]

# 时间复杂度 O(N^2)：其中固定指针k循环复杂度 O(N)，双指针 i，j 复杂度 O(N)。
    # 空间复杂度 O(1)：指针使用常数大小的额外空间。
    ''' 解析： 增加三个指针i,j,k 其中k是定位指针, i,j是扫描指针 流程 1.对给定序列进行排序 2.k从头定位 3.i指向k+1, j指向n-1 4.k.v+i.v+j.v 大于0 j左移, 小于0, i右移,直到j<k停止, k右移 如此k只需要一个循环, i,j只需要n个循环即可搞定,因此时间复杂度是O(N^2) '''
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            res = []
            if len(nums) < 3:
                return res
            nums.sort()
            if nums[0]>0:
                return res
            for k in range(len(nums)-2):
                if nums[k]>0:  # k.v < i.v < j.v
                    break
                if k>0 and nums[k]==nums[k-1]:
                    continue
                i = k + 1
                j = len(nums)-1
                while i<j:
                    sum = nums[i]+nums[j]+nums[k]
                    if sum == 0:
                        res.append([nums[k], nums[i], nums[j]])
                        i+=1
                        j-=1
                        while i<j and nums[i] == nums[i-1]: i+=1  # 去重
                        while i<j and nums[j] == nums[j+1]: j-=1 
    
                    elif sum<0:
                        i+=1
                        while i<j and nums[i] == nums[i-1]: i+=1 # 去重
                    elif sum>0:
                        j-=1
                        while i<j and nums[j] == nums[j+1]: j-=1 # 去重 
            return res
            
    def  main():
        solution = Solution()
        nums = [-1,0,1,2,-1,-4]  #[-4, -1, -1, 0, 1, 2]
        print(solution.threeSum(nums))
        pass
    
    if __name__ == '__main__':
        main()

![图解法结果][20200131110232800.png]

## 题解3 哈希表 ##

### 值得学习之处 ###

1.  遇到查找题型时,第一想到的应该就是**哈希表**,因为哈希表查找就跟数组索引一样,将直接进行地址查找,无需遍历无需计算,时间最短
2.  对比所有编程语言,Python和Javascrap对于字典建立哈希表较为方便, 而编程语言学习的就是其思想,我个人认为了解了哈希表的算法,使用最简单的语言解决最复杂的问题是最高效做事方法,同时值得介绍一下Python,其实很多Python的方法底层都是C,C++实现的,Python不过是一个搬砖工人,但是作为程序员,如果能够熟练使用搬砖工人,我们就不用自己变成一个搬砖工人,本人还是提倡高效搬砖,毕竟,所有语言都一样都是在搬砖.
3.  **结果去重时使用哈希表, 也是一种技巧,回答上面问题:**,  
    比如: 感谢问答 https://ask.csdn.net/questions/765148
    
        for key in list1:
           if key in list2:
    
    时间复杂度O(n^2)  
    如果觉得复杂度高的话可以考虑改用字典，或集合。  
    python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)。
4.  注意`for j,second in enumerate(nums[i+1:]):`  
    这里的j依旧是从0开始,不要误认为是从i+1开始  
    `if third_index == i or third_index == j+i+1:continue`  
    这里使用`j+i+1`就解释了上面  
    其实这里实质上是  
    `if third_index == i or third_index == j: continue`

<table> 
 <thead> 
  <tr> 
   <th align="center">哈希表</th> 
   <th align="center">方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">hashmap_res</td> 
   <td align="center">保存不重复结果,用于结果去重</td> 
  </tr> 
  <tr> 
   <td align="center">hashmap_nums</td> 
   <td align="center">建立nums的哈希表, 格式{负nums.value : nums.i}</td> 
  </tr> 
 </tbody> 
</table>

''' 解释: 建立hashmap_nums,保存-c, 创建双循环for i,num in enumerate(nums): first + second 判断等于 hashmap中的数据,从而得到结果索引 建立hashmap_res,保存不重复的结果字符串 '''
    
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            if len(nums)<3:
                return []
            nums.sort()
            res = []
            hashmap_res = { }
            hashmap_nums = { -num:i for i,num in enumerate(nums)}
            for i,first in enumerate(nums):
                if i > 0 and first == nums[i - 1]:
                    continue
                for j,second in enumerate(nums[i+1:]):
                    if first+second in hashmap_nums:
                        third_index = hashmap_nums[first+second]
                        if third_index == i or third_index == j+i+1:
                            continue
                        res_swap = sorted([first, second, nums[third_index]])
                        # if res_swap not in res:
                        # res.append(res_swap)
                        key = ",".join([str(num) for num in res_swap])
                        if key not in hashmap_res:
                            hashmap_res[key] = True
                            res.append(res_swap)
            print(res)
            return res

![哈希表结果][20200131110632494.png]

# 题目4 四数之和 利用哈希解锁 #

class Solution(object):
        def fourSum(self, nums, target):
            """ :type nums: List[int] :type target: int :rtype: List[List[int]] """
            hashmap_res = { }
            res = []
            nums.sort()
            print(nums)
            # a + b + c + d = target -> a + b + c = target-d
            hashmap_d = { target-num:i for i,num in enumerate(nums)} # 去除目标d的哈希表
            print(hashmap_d)
            for i,num_i in enumerate(nums[0:]):
                for j,num_j in enumerate(nums[i+1:]):
                    for k,num_k in enumerate(nums[j+2:]):
                        if num_i+num_j+num_k in hashmap_d:
                            index_d = hashmap_d[num_i+num_j+num_k]
                            if index_d==i or index_d==j+i+1 or index_d==k+j+2:
                                continue
                            if j+i+1 == k+j+2:
                                continue
                            if i == k+j+2:
                                continue
                            else:
                                res_swap = sorted([num_i, num_j, num_k, nums[index_d]])
                                key = ','.join([str(num) for num in res_swap])
                                if key not in hashmap_res:
                                    print([num_i, num_j, num_k, nums[index_d]])
                                    print(i,j+i+1,k+j+2,index_d)
                                    hashmap_res[key] = True
                                    res.append(res_swap)
    
            return res

# 总结: #

在以上两个题深入理解之后,对于遇到这种搜索题解第一想到的就是哈希表,无论是in or not in 都是遍历搜索,不如哈希表直接索引速度快.

[20200131120649921.png]: https://img-blog.csdnimg.cn/20200131120649921.png
[20200131121746695.png]: https://img-blog.csdnimg.cn/20200131121746695.png
[20200131165856242.png]: https://img-blog.csdnimg.cn/20200131165856242.png
[20200131164814421.png]: https://img-blog.csdnimg.cn/20200131164814421.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020013109260633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5,size_16,color_FFFFFF,t_70
[20200131110232800.png]: https://img-blog.csdnimg.cn/20200131110232800.png
[20200131110632494.png]: https://img-blog.csdnimg.cn/20200131110632494.png