Example 31
两个数组的交集
题目概述：给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
解题思路：如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，需要额外记录变量pre表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于pre，将该数字添加到答案并更新pre变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
解题步骤：
1. 将数组nums1、nums2排序。
2. 定义变量length1、length2分别存储两个数组的长度。
3. 定义数组intersection存储两个数组的交集元素，其长度为length1的length2的最小值（两个数组的交集最多为两个数组长度的最小值）。定义变量index、index1、index2分别记录交集数组、nums1、nums2当前考察的元素索引，初值均为0。
4. 定义while循环，若index1 < length1并且index2 < length2，说明当前还未考察完毕，继续进入循环考察，否则说明至少有一个数组已经考察完毕，则退出该循环。并将交集数组中的第0到index之间的元素（交集元素）复制到新数组中并返回。
5. 在while循环中，定义变量num1、num2分别记录两个数组中当前考察的元素。若num1等于num2，则将需要将该元素加入到交集数组中，且应当保证加入元素的唯一性，因此需要进一步判断是否index为0或者该元素是否不等于交集数组中的上一个元素，若是，则表明该元素在交集数组中是唯一的，将其加入到交集数组中，并将交集数组的考察索引自加一，而后分别将index1、index2自加一，考察下一元素。
6. 若num1小于num2，则表明nums1[index1]元素一定不是交集元素（因为nums2是递增的），则将index1自加一，继续判断下一个元素是否是交集元素，否则说明num1大于num2，表明nums2[index2]元素一定不是交集元素（因为nums1是递增的），则将index2自加一，继续判断下一个元素是否是交集元素。
示例代码如下：
public class ArrayIntersection { /** * 给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。 * 示例 1： * 输入：nums1 = [1,2,2,1], nums2 = [2,2] * 输出：[2] * 示例 2： * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] * 输出：[9,4] * 解释：[4,9] 也是可通过的 * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/intersection-of-two-arrays */ public static void main(String[] args) { ArrayIntersection ai = new ArrayIntersection(); System.out.println(Arrays.toString(ai.intersection(new int[]{1, 2, 2, 1}, new int[]{2, 2}))); // [2] } /** * 官方（个人修改） * * @param nums1 * @param nums2 * @return */ public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length, length2 = nums2.length; // int[] intersection = new int[length1 + length2]; 原官方 int[] intersection = new int[Math.min(length1, length2)]; int index = 0, index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { int num1 = nums1[index1], num2 = nums2[index2]; if (num1 == num2) { // 保证加入元素的唯一性 if (index == 0 || num1 != intersection[index - 1]) { intersection[index++] = num1; } index1++; index2++; } else if (num1 < num2) { index1++; } else { index2++; } } return Arrays.copyOfRange(intersection, 0, index); } }
