349.两个数组的交集.md

349 两个数组的交集

题目：
给定两个数组，编写一个函数来计算它们的交集。

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

思路：
由于检查一个元素是否在set中的时间复杂度为O(1),而且set中不包含重复元素。因此考虑用Hashset数据结构来解决。 准备两个set，将nums1中元素加进set1中，将nums2中元素加进set2中。遍历set1中的元素，若其也在set2中，则将此元素加入到结果数组中。

代码：

public int[] intersection(int[] nums1, int[] nums2) {
    if(nums1 == null || nums2 == null)
        return null;
    Set<Integer> set1 = new HashSet<Integer>();
    Set<Integer> set2 = new HashSet<Integer>();
    for(int nums: nums1)
        set1.add(nums);
    for(int nums:nums2)
        set2.add(nums);
    List<Integer> list = new ArrayList<Integer>();
    for(int num:set1){
        if(set2.contains(num))
            list.add(num);
    }
    int[] res = new int[list.size()];
	for(int i = 0; i < list.size();i++)
        res[i] = list.get(i);  
    return res;
  }
}

list数据结构在定义时不需要声明大小。上述方法先将结果都加入到list中，再建立一个和list大小相同的数组，将list中的元素都加入到这个数组中，并返回。 注：list的添加操作为add，提取操作为get

也可以不用list，直接用数组来解决。

int [] res = new int[Math.max(set1.size(),set2.size())];
int idx = 0;
for (int num : set1){
    if (set2.contains(num)) 
        res[idx++] = num;
return Arrays.copyOf(res, idx);