数据结构-哈希表（二）

1.两个数组的交集

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

class Solution:
    def intersect(nums1, nums2) :
        hashMap=collections.defaultdict(int)
        res=[]
        for i in range(len(nums1)):
                hashMap[nums1[i]]+=1
        for i in range(len(nums2)):
                if hashMap[nums2[i]]!=0:
                    res.append(nums2[i])
                    hashMap[nums2[i]]-=1
        return res

2.两个数的交集Ⅱ

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

def intersect(nums1, nums2):
        hashMap=collections.defaultdict(int)
        res=[]
        for i in range(len(nums1)):
                hashMap[nums1[i]]+=1
        for i in range(len(nums2)):
                if hashMap[nums2[i]]!=0:
                    res.append(nums2[i])
                    hashMap[nums2[i]]-=1
        return res

 3.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

 

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

def getSum(n):
    nums=0
    while n:
        nums+=(n%10)**2
        n=n//10
    return nums
def isHappyNumber(n):
    s=set()
    n=getSum(n):
    while n:
        if n==1:
              return True
        if n in mid:
               return False
        else:
            s.add(n)

 4.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

 (1)暴力解法

循环遍历时间复杂度为O(n^2)

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

 (2)使用集合，时间复杂度为O(n)

def getSum(nums,target):
        #创建一个集合来存储我们目前看到的数字
        seen = set()             
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [nums.index(complement), i]
            seen.add(num)

5.四数相加

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

1.暴力解法

这道题用暴力时间复杂度较大，为O(n^4) 

def fourSumCount(nums1, nums2, nums3 nums4):
                    res = 0
                    for i in range(len(nums1)):
                        for j in range(len(nums2)):
                            for k in range(len(nums3)):
                                for h in range(len(nums4)):
                                    if nums1[i]+nums2[j]+nums3[k]+nums4[h]==0:
                                        res+=1
                    return res

2. 使用哈希表，该题与两数之和有点类似

 def fourSumCount(nums1, nums2, nums3, nums4)
             hashMap=collections.defaultdict(int)
             for i in range(len(nums1)):
                    for j in range(len(nums2)):
                         hashMap[nums1[i]+nums2[j]]+=1
             res=0
             for i in range(len(nums3)):
                    for j in range(len(nums4)):
                       if hashMap[0-nums3[i]-nums4[j]] !=0:
                             res+=hashMap.get(0-nums3[i]-nums4[j])
             return res