leetcode-349：两个数组的交集

问题

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

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

示例2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]；输出：[9,4]

方法一：两个数组

计算两个数组的交集，遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。假设数组 nums1 和 nums2 的长度分别是 m 和 n，则遍历数组 nums1 需要 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 的时间，因此总时间复杂度是

如果使用哈希集合存储元素，则可以在 的时间内判断一个元素是否在集合中，从而降低时间复杂度

• 首先使用两个集合分别存储两个数组中的元素
• 遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值

该方法的时间复杂度可以降低到

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) {
            set2.add(num);
        }
        return getIntersection(set1, set2);
    }
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        if (set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }
        return intersection;
    }
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/
来源：力扣（LeetCode）

• 时间复杂度：，其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 的时间，因此总时间复杂度是
• 空间复杂度：，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于两个集合

方法二：排序+双指针

首先对两个数组进行排序，然后使用两个指针遍历两个数组。加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 表示上一次加入答案数组的元素
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于，将该数字添加到答案并更新 变量，同时将两个指针都右移一位，当至少有一个指针超出数组范围时，遍历结束

package leetcode;
import java.util.Arrays;
public class leetcode_349 {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
        //将一个原始的数组original，从下标 0 开始复制，复制到上标 index ，生成一个新的数组,
          注意这里包括下标 0 ，不包括上标 index ;效率和clone基本一致，比利用循环复制数组效率高
}

https://mp.weixin.qq.com/s/N9iqAchXreSVW7zXUS4BVA
链接方法中有用到哈希数据结构，包括C++代码