## 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映射
- 双指标解法
- 递归来交换数组

01|俩个数组交集(350)