[数据结构与算法]LeetCode——349. 两个数组的交集

1.问题描述

2.解决办法

1. 排序+双指针

排序后 第一数组用指针index1指向 第二数组用指针index2指向
index1指向和index2指向比较如果相等放入新数组
如果index1<index2将index1右移动
如果index1>index2将index2右移动
如果index1=index2将index1和index2同时右移动

该函数Arrays.copyOfRange函数是将intersection从0到index复制到一个新数组中

3.代码实现

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);
    }
}