349. 两个数组的交集

题目链接 link

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

思路 1

将两个 list 转换为 set（确保一个数字在一个 list 中只存在一次），然后分别进行遍历，统计所有数字出现的次数，出现次数为 2 的即为交集。本质上是用 dict 作为哈希表。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c = Counter()
        res = []
        for i in set(nums1):
            c[i] += 1
        
        for i in set(nums2):
            c[i] += 1
        
        for key in c:
            if c[key] > 1:
                res.append(key)
        return res

思路 2

一步到位，直接使用 set 的 & 操作符来计算交集。

1
2
3

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

350. 两个数组的交集 II

题目链接 link

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

示例 1：

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

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路

用 dict 来记录两个 list 中数字的数量，然后判断重叠部分的数量。

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c1 = Counter()
        c2 = Counter()

        for i in nums1:
            c1[i] += 1
        
        for i in nums2:
            c2[i] += 1
        res = []
        for key in c1:
            if c1[key] > 0 and c2[key] > 0:
                for i in range(min(c1[key], c2[key])):
                    res.append(key)
        return res
        '

202. 快乐数

link

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

「快乐数」定义为：

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

思路

用一个 set 记录出现过的结果，如果出现过了该结果，则说明不是快乐数

class Solution:
    def isHappy(self, n: int) -> bool:
        s = 0
        l = set()
        while s != 1:
            s = 0
            while n != 0:
                temp = n % 10
                s += temp * temp

                n = n // 10
            
            if s in l:
                return False

            else:
                if s == 1:
                    return True
                l.add(s)
                n = s

注意，虽然 set 和 list 都是用 in 来判断是否存在，但是其复杂度差很多：

1. 两数之和

link

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

示例 1：

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

思路

本质上是查找，所以可以使用 set 进行查找，但是又需要返回下标，所以使用 dict 作为哈希表。使用 nums 中的值作为 key，使用下标作为 value。可以写出以下代码：

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

        for i in range(len(nums)):
            d[nums[i]] = i

        for i in range(len(nums)):
            if target - nums[i] in d:
                return [i, d[target - nums[i]]]

乍一看没问题，但是，题目要求不能使用两个相同的数，例如输入 nums=[3, 2, 4]，target=6 时，上述代码会返回 [0, 0]。问题在于我们先把所有的数都存入哈希表了，这样查询 3 的时候就会直接返回，而不会再去查询 2。事实上不需要将所有的数都预先存到哈希表中，这是因为即使遍历到 2，此时 4 还没有加入哈希表，但是遍历到 4 时，2 已经加入了，所以一定会找到答案。（题目中也暗示可以按照任意顺序返回答案）

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

        for i in range(len(nums)):
            if target - nums[i] in d:
                return [i, d[target - nums[i]]]
            d[nums[i]] = i

对比：

list 的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set 是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用

454. 四数相加 II

link

给你四个整数数组 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
解释：
两个元组如下：
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

思路

数组两两配对相加，分别计算出可能的和，然后就退化成两数之和。注意两个数组的和可能又多种可能，所以需要使用使用 Counter 作为哈希表。

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        sum1 = Counter()
        sum2 = Counter()
        for i in nums1:
            for j in nums2:
                sum1[i + j] += 1
        
        for i in nums3:
            for j in nums4:
                sum2[i + j] += 1
        res = 0
        for i in sum1:
            if 0 - i in sum2:
                res += sum2[0 - i]
        
        return res