[数据结构与算法]LeetCode.350：两个数组的交集II

题目

思路

对于两个数组的交集，其实就是寻找两个数组的相同元素，所以可以使用双指针。将两个数组分别进行排序，然后定义指针i和j，分别指向nums1和nums2的第0个位置。当i所指向的位置元素大于j指向的位置时，i不动，j+1；反之j不动，i+1。当i和j指向的位置元素相等时，证明此数字是两个数组的交集之一，则将它添加进用于存放结果的动态数组。因为两个数组是经过排序的，所以若i和j其中有一个的值大于数组的长度，则退出循环，表示无交集。

代码

public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while(i < nums1.length && j < nums2.length) {
            if(nums1[i] < nums2[j])
                i++;
            else if(nums1[i] > nums2[j])
                j++;
            else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[list.size()];
        for(int k = 0;k < list.size();k++) {
            res[k] = list.get(k);
        }
        return res;
    }