前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
链表的合集
题目
给定两个数组 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] 也是可通过的
题解
其实这题也很简单，也是我们实际开发过程中 会经常碰到的，取2个数组的交集去重，其实思路有2个，一个是通过遍历2个数组，吧值变成map,然后判断另外一个map是不是包含循环这个的值，如果有就加入到结果中，这种就是我们map的方法
第二个方式，就是我们数组排序，排序之后用双指针的方式，就是同时往后移动指标，如果当前有相等就加入，然后2个指针同时往前走，不然就小的往前走，一直走到其中的一个指针超过了最大值，这种就是我们所说的双指针法
两个集合Map
计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。假设数组 nums1 和 nums2 的长度分别是 mm 和 nn，则遍历数组 nums1 需要 O(m)O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n)O(n) 的时间，因此总时间复杂度是 O(mn)O(mn)。
如果使用哈希集合存储元素，则可以在 O(1)O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)O(m+n)
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); for (int num : nums1) { set1.add(num); } for (int num : nums2) { set2.add(num); } return getIntersection(set1, set2); } public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) { if (set1.size() > set2.size()) { return getIntersection(set2, set1); } Set<Integer> intersectionSet = new HashSet<Integer>(); for (int num : set1) { if (set2.contains(num)) { intersectionSet.add(num); } } int[] intersection = new int[intersectionSet.size()]; int index = 0; for (int num : intersectionSet) { intersection[index++] = num; } return intersection; } }
排序 + 双指针
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量pre 表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
class Solution { 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 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); } }
结束
好了，这题就到这了，其实这题还是蛮简单的，大家看下应该很快就会写了，我是小六六，三天打鱼，两天晒网！
