Leetcode-350-两个数组的交集 II

给定两个数组，写一个方法来计算它们的交集。

例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

分析：

这道题意思很明显，找出两个数组都存在的元素。这道题本身不难，就算是遍历穷举的方法也能做出来，但肯定会导致时间复杂度高，不够优雅。如何寻找巧妙的方法？
我们可以先递增排序，这样可以利用顺序来过滤掉已经不可能出现交集的元素，再定义两个脚标变量，这两个变量都从0开始，向后遍历，如果两个数组的值相同，存下这个值，两个脚标同时加1；如果两个数组的值不同，那么值较小的数组脚标值加1，另一个脚标值等待……直到遍历完短的那个数组……

由上分析，Java解答如下：

    public int[] intersect(int[] nums1, int[] nums2) {

        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[]{};
        }

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0;
        int j = 0;
        int k = 0;
        int length1 = nums1.length;
        int length2 = nums2.length;

        int[] result = new int[Math.min(length1, length2)];
        while (i < length1 && j < length2) {
            if (nums1[i] == nums2[j]) {
                result[k] = nums1[i];
                k += 1;
                i += 1;
                j += 1;
                continue;
            }

            if (nums1[i] > nums2[j]) {
                j += 1;
            } else {
                i += 1;
            }
        }

        return Arrays.copyOf(result, k);
    }

最后使用的Arrays.copyOf(original, newLength)很有意思，其中original可以是各种类型的数组，这个方法可以将数组origianl的前newLength个元素拷贝入一个新的数组，新数组的长度和指定的数值一样。因为在遍历开始之前，无法知道结果数组的真实长度，只能输入最大的可能值（两个数组的长度中小的那个），而返回的结果是要求长度和交集数一致的。如果使用ArrayList中转一下，会显得很不自然优雅，而这个方法可以很好的解决这个问题。