``` 给定两个数组，编写一个函数来计算它们的交集。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2: 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9] 说明： 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。 我们可以不考虑输出结果的顺序。 进阶： 如果给定的数组已经排好序呢？你将如何优化你的算法？ 如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ ``` >此题可以看成是一道传统的映射题（map映射），为什么可以这样看呢，因为我们需找出两个数组的交集元素，同时应与两个数组中出现的次数一致。这样就导致了我们需要知道每个值出现的次数，所以映射关系就成了<元素,出现次数>。剩下的就是顺利成章的解题。 代码如下： ``` public class IntersectionOfTwoArrays { public static int[] intersect(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { intersect(nums2, nums1); } Map<Integer, Integer> map = new HashMap(); for(int num : nums1) { // getOrDefault(object, defaultvalue)方法就是先get()，如果返回为空，则返回默认值 // 这里的意思是，遍历数组，统计每个数字出现的次数，最小出现1次 int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } // 新数组下标，长度 int index = 0; // new 一个新数组 int newNum[] = new int[nums1.length]; // 遍历另外一个数组 for (int num : nums2) { int count = map.getOrDefault(num, 0); // 大于0 则表示该数字在另一个数组出现过 if (count > 0) { // 将其加到新数组 newNum[index++] = num; // 次数减去1 count--; // 大于0 表示该数字存在多次，将减1后的次数覆盖到原来的次数上 if (count > 0) { map.put(num, count); } else { // 小于或者等于0则删除 map.remove(num); } } } // Arrays.copyOfRange(T[ ] original,int from,int to) // 将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。 return Arrays.copyOfRange(newNum, 0, index); } public static void main(String[] args) { int[] num1 = new int[]{1,2,2,1}; int[] num2 = new int[]{2,2}; int[] num3 = intersect(num1, num2); } } ``` 进阶方法： >如果两个数组是有序的，则可以便捷地计算两个数组的交集。 > >首先对两个数组进行排序，然后使用两个指针遍历两个数组。 > >初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。 代码如下： ``` public static int[] intersect1(int[] nums1, int[] nums2) { // 排序 Arrays.sort(nums1); Arrays.sort(nums2); int index1 = 0; int index2 = 0; int index3 = 0; int length1 = nums1.length; int length2 = nums2.length; // 构建新数组 int newNum[] = new int[Math.min(length1, length2)]; while (index1 < length1 && index2 < length2) { if (nums1[index1] < nums2[index2]) { index1++; } else if (nums1[index1] > nums2[index2]) { index2++; } else { newNum[index3] = nums1[index1]; index1++; index2++; index3++; } } return Arrays.copyOfRange(newNum, 0, index3); } ```