两个数组的交集 II about pisecespeng.record.me HOT 3 CLOSED

// 排序 基于给定的数组已排序
// Arrays.sort(nums1); Arrays.sort(nums2);
private static int[] func(int[] nums1, int[] nums2) {
    int length1 = nums1.length, length2 = nums2.length;
    int index1 = 0, index2 = 0, indexRes = 0;

    // 存放结果的数组
    int[] res = new int[length1 > length2 ? length1 : length2];
    // 当有一个数组结束遍历, 则终止全部遍历
    // 双指针, 判断指针指定的值大小, 来挪动指针位置
    while (index1 < length1 && index2 < length2) {
        if (nums1[index1] == nums2[index2]) {
            res[indexRes++] = nums1[index1];
            index1++;
            index2++;
        }
        else if (nums1[index1] > nums2[index2]) {
            index2++;
        }
        else index1++;
    }
    // 截取结果
    return Arrays.copyOf(res, indexRes);
}

public static int[] func(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int length1 = nums1.length, length2 = nums2.length;
    int[] intersection = new int[Math.min(length1, length2)];
    int index1 = 0, index2 = 0, index = 0;
    while (index1 < length1 && index2 < length2) {
        if (nums1[index1] < nums2[index2]) {
            index1++;
        } else if (nums1[index1] > nums2[index2]) {
            index2++;
        } else {
            intersection[index] = nums1[index1];
            index1++;
            index2++;
            index++;
        }
    }
    return Arrays.copyOfRange(intersection, 0, index);
}

public static int[] func(int[] nums1, int[] nums2) {
    // 可以通过遍历较短的数组, 来降低空间复杂度
    if (nums1.length > nums2.length) {
        return func(nums2, nums1);
    }
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int num : nums1) {
        int count = map.getOrDefault(num, 0) + 1;
        map.put(num, count);
    }
    int[] intersection = new int[nums1.length];
    int index = 0;
    for (int num : nums2) {
        int count = map.getOrDefault(num, 0);
        if (count > 0) {
            intersection[index++] = num;
            count--;
            if (count > 0) {
                map.put(num, count);
            } else {
                map.remove(num);
            }
        }
    }
    return Arrays.copyOfRange(intersection, 0, index);
}