349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.

• The result can be in any order.

解题要点：

分别将两条char数组存入HashSet里，以便于后面的比较。根据判断两个set的长短，由短的那条作为遍历标准，并在里面判断是否有相同数，把数加入一条新数组里，最后返回新数组的值。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
    	int[] res = new int[nums1.length];
    	int k = 0;
    	HashSet<Integer> n1 = new HashSet();
    	for(int i : nums1) n1.add(i);
    	HashSet<Integer> n2 = new HashSet();
    	for(int j : nums2) n2.add(j);
    	
    	if(n1.size() < n2.size()) {
	    	for(int l : n1) {
	    		if(n2.contains(l))
	    			res[k++] = l;
	    	}
    	}else {
	    	for(int l : n2) {
	    		if(n1.contains(l))
	    			res[k++] = l;
	    	}    		
    	}
    	
    	return Arrays.copyOf(res, k);
    }
}

Complexity Analysis

• Time complexity O(n + m), where n and m are arrays' lengths. O(n)time is used to convert nums1 into set, O(m) time is used to convert nums2, and contains/in operations are O(1) in the average case.

• Space complexity : O(m+n) in the worst case when all elements in the arrays are different.