LeetCode 查找表专题 1：查找问题简介

这一部分，我们开始学习查找表相关问题。

查找，是使用计算机处理问题时的一个最基本的任务，因此也是面试中非常常见的一类问题。很多算法问题的本质，就是要能够高效查找。学会使用系统库中的 map 和 set，就已经成功了一半。

常见的两类查找问题是：

• 查找有无；
• 查找是否存在对应的关系。

通常语言的标准库中都内置了 set 和 map 这两种数据结构，并且给出了不同的实现，例如 Java 中 Set 的实现有 HashSet、LinkedHashSet 等，我们可以直接利用这些现成的数据结构的 API （增删改查）来帮助我们解答问题。
下面来看一个非常简单的问题。

例题1：LeetCode 第 349 题：Intersection of Two Arrays

传送门：英文网址：349. Intersection of Two Arrays ，中文网址：349. 两个数组的交集 。

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

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

示例 2:

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

说明:

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

分析：给定两个数组，求出这两个数组的公共元素。要求：1、结果中的元素是唯一的；2、无序。
​思路：使用两个集合作为中转。第 1 个集合，把 nums1 的元素放进去，去除重复。
​Java 代码：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();

        for (int num : nums1) {
            set1.add(num);
        }

        for (int num : nums2) {
            if (set1.contains(num)) {
                set2.add(num);
            }
        }


        int[] result = new int[set2.size()];

        int index = 0;
        for (int num : set2) {
            result[index++] = num;
        }

        return result;
    }
}

Python 代码：

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        s = set(nums1)
        return list({ele for ele in nums2 if ele in nums1})

Python 代码：

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        a = set(nums1)
        b = set(nums2)
        c = a & b
        return list(c)

说明：在 C++ 中，Set 和 Vector 对于元素是否存在的处理有不同，这里有一个坑，以后学习了 C++ 再来补充。

Python 代码：

class Solution:

    # 求出两个数组的交集

    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # 让 num1 是元素多的那个数组
        if len(nums1) == len(nums2):
            nums1, nums2 = nums2, nums1
        # 去重复
        s = set(nums1)
        # 这一步在 nums2 里面的操作就变少了
        return list({x for x in nums2 if x in s})


# 解法2：
# return list(set(nums1) & set(nums2))

# 解法3：
# return list(set(nums1).intersection(set(nums2)))

# 解法4：
# nums1 = set(nums1)
# nums2 = set(nums2)
# return list(nums1 & nums2)

# 解法5：
# return list({x for x in nums2 if x in nums1})


if __name__ == '__main__':
    solution = Solution()
    nums1 = [1, 2, 2, 1]
    nums2 = [2, 2]
    result = solution.intersection(nums1, nums2)
    print(result)

（本节完）