[数据结构与算法]LeetCode知识点总结 - 350

LeetCode 350. Intersection of Two Arrays II

题目

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

重点

因为这道题不要求结果不重复，所以用简单的two pointers方法就可以。大概思路：
新建空array用来存储结果，长度设置为nums1.length和nums2.length中更小的一个。从小到大对两个arrays进行排序。设置三个pointers，pointer1对应nums1，pointer2对应nums2，pointer3用来计数。比较nums1[pointer1]和nums2[pointer2]，如果前者大则pointer2++，反之pointer1++，相等则将数值存储到新建的array，pointer1和pointer2同时加一。

答案

public int[] intersect(int[] nums1, int[] nums2) {
	Arrays.sort(nums1);
	Arrays.sort(nums2);
	int i=0,j=0,k=0;
	int[] output = new int[Math.min(nums1.length, nums2.length)];
	while(i<nums1.length && j<nums2.length){
		if(nums1[i]<nums2[j] )
			i++;
		else if(nums2[j]<nums1[i])
			 j++;
		else if(nums1[i]==nums2[j]){
			output[k++]=nums1[i];
			i++;            
			j++;
		}
	}
	return Arrays.copyOfRange(output, 0, k);
   }

*也可以不新建array，直接在nums1里面改值，最后返回前k个值。因为k总小于等于i，所以不会出问题。根据我提交答案的结果，新建array会比不新建稍快一点。