刷题总结：使用Python-哈希表——两数之和、两个数组的交集

50 阅读 0 评论 33 点赞

我是靠谱客的博主可耐钢笔，最近开发中收集的这篇文章主要介绍刷题总结：使用Python-哈希表——两数之和、两个数组的交集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

KW49/20：学习了哈希表的知识，一共练习1个题目，现在总结如下。

第一题：两数之和，给定一个数组和一个目标值，在数组中找出和为目标值的两个数，并返回下标。

思路：首先想到的是双重循环，枚举数组中的每一个数，看target-x是否在数组中。代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        n = len(nums)
        for i in range(0, n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []

但是上述双重循环方法时间复杂度高，考虑使用哈希表来降低时间复杂度。代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        hash_table = dict()
        for i, num in enumerate(nums):
            if target - num in hash_table:
                return [hash_table[target-num], i]
            else:
                hash_table[num] = i

第二题：两个数组的交集，给定两个数组，给出他们的交集。

思路：首先想到的是用集合给数组去重，然后遍历集合中的每一个数，看另一个集合中是否存在。代码如下：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        nums1 = set(nums1)
        nums2 = set(nums2)
        res = []
        for num1 in nums1:
            if num1 in nums2:
                res.append(num1)

        return res

也可以使用集合求交集的命令，代码更加简化：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        nums1 = set(nums1)
        nums2 = set(nums2)
        res = []
        res = nums1 & nums2  # 集合求交集
        # for num1 in nums1:
        #     if num1 in nums2:
        #         res.append(num1)

        return res