LeetCode 349. 两个数组的交集（简单、数组）day12

题目描述：给定两个数组 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] 也是可通过的

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

结题思路：

方法一：排序 + 双指针

1、先声明一个List集合，用于存储两个数组中相同的元素，不用数组的原因在于数组长度固定，不知道有多少个元素相同，所以最好使用集合；
2、先对两个集合进行排序；
3、遍历两个数组找出同样的元素，把相同的元素加入到集合中，但是在加入集合之前一定要判断一下元素在集合中是否已经存在，如果已经存在则放弃添加；
4、把集合中的元素添加到数组中，返回数组即可。

方法二：使用HashSet集合

1、声明两个Set集合，set1, set2（Set集合的基本特性为无序，无索引，不可重复）；
2、把数组nums1中的元素添加到set1集合中；
3、遍历数组nums2，判断nums2中的元素是否在set1集合中存在，如果存在则添加到set2集合中，否则放弃该元素，直到遍历结束；
4、把set2集合中的元素复制到数组中即可，最后返回数组。

如果想要详细了解Collection集合体系中的Set和List集合，可以参考文章：https://blog.csdn.net/qq_43751200/article/details/123803851

代码实现：

public class Intersection {
    public static void main(String[] args) {
        int[] nums1 = {4,9,5};
        int[] nums2 = {9,4,9,8,4};
        System.out.println(Arrays.toString(intersection1(nums1, nums2)));
    }

    // 方法1： 排序 + 双指针
    public static int[] intersection(int[] nums1, int[] nums2) {
        // 1. 声明一个List集合
        List<Integer> list = new ArrayList<>();

        // 2. 对数组nums1, nums2进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 3. 遍历数组找到相同的元素
        int m = 0, n = 0;
        while (m < nums1.length && n < nums2.length){
            if(nums1[m] == nums2[n]){
                if(list.contains(nums1[m])){
                    // 如果集合中已经存在了，什么都不需要做了
                }else {
                    list.add(nums1[m]);
                }
                // 指针都需要向前移动
                m++;
                n++;
            }else if(nums1[m] > nums2[n]){
                n++;
            }else {
                m++;
            }
        }

        // 4. 把list数组转化为数组
        int[] nums = new int[list.size()];
        for(int i = 0; i < nums.length; i++){
            nums[i] = list.get(i);
        }

        return nums;
    }

    // 方法2：Set集合
    public static int[] intersection1(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();    // HashSet特性：无序、不重复、无索引。
        Set<Integer> set2 = new HashSet<>();

        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }

        for(int i = 0; i < nums2.length; i++){
            if(set1.contains(nums2[i])){
                set2.add(nums2[i]);
            }
        }

        int[] nums = new int[set2.size()];
        int k = 0;
        for(Integer it : set2){
            nums[k++] = it;
        }
        return nums;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays