给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
题目描述：给定两个数组，求它们的交集。
解题思路：使用哈希表记录一个数组中各个元素出现的次数，然后遍历另一个数组，如果当前元素在哈希表中出现过，就将它加入结果集，并在哈希表中将其出现次数减一。
这是因为我们要求的是两个数组的交集，即两个数组中共同出现的元素，而一个元素在两个数组中出现的次数，应该等于其在两个数组中出现次数的较小值。因此，在哈希表中将其出现次数减一，是为了避免重复计数。如果不将其出现次数减一，就会导致重复计数，结果集中会出现重复元素。
具体实现：
1.首先判断两个数组的长度，将较短的数组作为第一个数组，方便后续操作。
2.定义一个哈希表，用于记录第一个数组中各个元素出现的次数。遍历第一个数组，将每个元素作为 key，其出现次数作为 value，存入哈希表中。
3.遍历第二个数组，对于每个元素，如果它在哈希表中出现过且出现次数大于 0，就将它加入结果集，并在哈希表中将其出现次数减一。
4.返回结果集。
时间复杂度：
需要遍历两个数组各一次，并对哈希表进行插入和查询操作，时间复杂度均为 O(m+n)，其中 m 和 n 分别是两个数组的长度。
空间复杂度：
对于较短的数组使用哈希表进行元素计数，空间复杂度是 O(min(m,n))。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp; // 保证 nums1 是长度较短的数组
}
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums1) {
map.put(num, map.getOrDefault(num, 0) + 1); // 记录 nums1 中各个元素出现的次数
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (map.containsKey(num) && map.get(num) > 0) { // 如果 nums2 中的当前元素在哈希表中出现过
list.add(num); // 将其加入结果集
map.put(num, map.get(num) - 1); // 在哈希表中将其出现次数减一
}
}
int[] res = new int[list.size()];
for (int i = 0; i < res.length; i++) {
res[i] = list.get(i);
}
return res;
}
}
进一步优化时间和空间复杂度，可以考虑使用双指针的方法，对两个数组进行排序，然后使用两个指针分别指向两个数组的开头，逐个比较它们指向的元素是否相等。如果相等，就将当前元素加入结果集，并将两个指针都向后移动一位；如果不相等，就将较小的元素所在的数组的指针向后移动一位。这样可以不使用哈希表，在时间复杂度上进一步优化，将时间复杂度降为 O(m log m + n log n)，其中 m 和 n 分别是两个数组的长度。但是这种方法的空间复杂度仍然是 O(1)，因为只需要常数级别的额外空间来存储指针和结果集。
以下是使用双指针的方法实现两个数组的交集，时间复杂度为 O(m log m + n log n)，空间复杂度为 O(1)：
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0, k = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
nums1[k++] = nums1[i++];
j++;
}
}
return Arrays.copyOfRange(nums1, 0, k);
}
其中，Arrays.sort() 方法用于对两个数组进行排序，Arrays.copyOfRange() 方法用于返回结果集。在代码中，使用三个指针 i、j 和 k 分别指向两个数组和结果集，逐个比较两个数组中的元素。如果两个元素相等，就将其加入结果集，并将两个指针都向后移动一位；如果不相等，就将较小的元素所在的数组的指针向后移动一位。最后，将结果集复制到一个新的数组中，并返回该数组。
不清楚的地方可留言或发简信
网友评论