不啰嗦，我们先进入正文，来一起头脑风暴，思考这道题目。
头脑风暴！！
题目
给定两个数组，编写一个函数来计算它们的交集。
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
示例
<code>输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]/<code>
<code>输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]/<code>
题解
针对这种求交集的题目，我们首先要想到，求交集，我们就需要知道每个元素出现的次数，才能够判断他在两个数组中出现的次数，也就是这道题存在一个明显的映射关系，那就是 元素 -> 出现的次数。
我们便可以按照传统的映射题来进行解答，也就是下面的题解1：
1、使用HashMap构建映射，获取交集元素：
我们先用一个HashMap记录短数组的元素，记录元素和每个元素出现的个数，再遍历另一个数组，用另一个数组的元素，逐个去HashMap里面比较，如果存在值，就将该元素取出来，同时要将Map里的次数减1，代表已经找到一个了，直到遍历结束，便将取出来的元素以数组形式返回。
<code>public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
HashMap<integer> m = new HashMap<>();
for (int n : nums1) {
m.put(n, m.getOrDefault(n, 0) + 1);
}
int k = 0;
for (int n : nums2) {
int cnt = m.getOrDefault(n, 0);
if (cnt > 0) {
nums1[k++] = n;
m.put(n, cnt - 1);
}
}
return Arrays.copyOfRange(nums1, 0, k);
}/<integer>/<code>2、双指针
另外一种解法，我们可以利用双指针的方法，对两个数组进行逐个的遍历和对比，通过指针移动，判断结束的时候，并得到结果。
当该方案，我们需要对数组进行排序，才能够使双指针可以按顺序的进行比较。
所以若题目提出了两个数组是有序数组的话，该方案会拥有更好的效率。
<code>public int[] intersect(int[] nums1, int[] nums2) {
\t// 这里我们先排个序，如果是有序数组，就不需要进行这个步骤
Arrays.sort(nums1);
Arrays.sort(nums2);
\t// 定义两个指针i和j，同时声明一个结果数组长度k
int i = 0, j = 0, k = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
\t\t\t// 如果nums1[i] 比 nums2[j]要小，说明 此时指针i所指的元素小于指针j所指向的元素，又是有序的，那么我们将i+1，进行下个比较
++i;
} else if (nums1[i] > nums2[j]) {
\t\t\t// 如果nums1[i] 比 nums2[j]要大，说明 此时指针i所指的元素大于指针j所指向的元素，又是有序的，那么我们将j+1，进行下个比较
++j;
} else {
\t\t\t// 当相等的时候，获得一个结果，直接放到nums1中，不浪费空间，同时三个指针+1，进行下个比较
nums1[k++] = nums1[i++];
++j;
}
}
\t// 比较结束后，我们将nums1从0到k的数组拿出来，便是我们的结果
return Arrays.copyOfRange(nums1, 0, k);
}/<code>这个解法的关键在于排序，排好序之后的两个数组，根据大小，才能进行指针的移动，从而进行比较和结果的获取。
分享到:
閱讀更多 居家程序員 的文章
