## 1.题目 给定两个数组，编写一个函数来计算它们的交集。 > 示例 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 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ ## 2.题解 初次做题，通过各种讲解，个人获取到到办法是通过映射办法（map映射）来解决。因为我们需要找出俩个数组到交集，同时应该与俩个数组中出现的最低次数一致。我们就必须统计每个值出现的次数，因此我们的映射关系就成了<元素，次数>。 ## 3.答案分析 ### 3.1 Code ```Java class Solution { public int[] intersect(int[] nums1, int[] nums2) { int[] temp = {}; if (nums1.length > nums2.length) { //nums1 与 nums2交换 temp = nums1; nums1 = nums2; nums2 = temp; } Map result = new HashMap(); for (int n : nums1 ) { int count = result.getOrDefault(n, 0) + 1; result.put(n, count); } int[] intersection = new int[nums1.length]; int index = 0; for (int num : nums2) { int count = result.getOrDefault(num, 0); if (count > 0) { intersection[index++] = num; count--; if (count > 0) { result.put(num, count); } else { result.remove(num); } } } return Arrays.copyOfRange(intersection, 0, index); } } ``` 简单问题，相对容易。初次写，效率略低。  ### 3.2 复杂度分析 - 时间复杂度：O（m+n）,m和n代表俩个数组的长度。 - 空间复杂度：O(min(m,n)),返回new int[nums1.length]取值为最小长度的数组。 ## 4.进阶分析 ## 4.1 重构 进阶问题是数组已经排好序，那么我们可以优化一下我们的算法。参考他人方法，此处我们可以使用“双指针”解法。 举例子：nums1=[2,3,7,9],nums2=[2,4,6,7] |2|3 |7 |9 | |-------|-------|-------|--|--| |2|4|6|7| ### 4.2 思路 设定俩个0开始的指针（index1，index2），比较这俩个指针所在的（nums1,nums2)的元素是否相等。 1. 如果俩元素相等，则将相同元素放到空白数组。并且index1，index2均向后移一位 2. 如果俩元素不相同，那么小的指针向后移。 3. 循环上面步骤 4. 直到任意一个数组结束 ### 4.3 优化 对于需要判断哪个数组长度问题，我们可以通过交换数组的方式，来让nums1始终为最小数组。 ## 5.进阶答案分析 ## 5.1 Code ```java class Solution { public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length; int length2 = nums2.length; if (length1 > length2) { return intersect(nums2, nums1); } int index = 0; int index1 = 0; int index2 = 0; int[] result = new int[length1]; while (index1 < length1 && index2 < length2) { if (nums1[index1] < nums2[index2]) { index1++; } else if (nums1[index1] > nums2[index2]) { index2++; } else { result[index] = nums1[index1]; index1++; index2++; index++; } } return Arrays.copyOfRange(result, 0, index); } } ```  ### 5.2 复杂度分析 - 时间复杂度：O(mlogm+nlogn)，对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是O(mlogm+nlogn) - 空间复杂度：O(min(m,n)),返回new int[nums1.length]取值为最小长度的数组。 ## 6.总结 从这第一次做题中，花费了我蛮多的时间去审题和编写。但是从我的第一题，我学到了几个知识点： - map映射 - 双指标解法 - 递归来交换数组