Leetcode 349：Intersection of Two Arrays

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

说人话：

给定两个数组 nums，求两个数组的公共元素。

几个要点：

• 结果中的元素不重复
• 元素顺序无所谓

[法1] 暴力法

思路

考虑到结果中元素不重复这个要求，就可以想到用 Set 了。直接双层循环，将 num1 和 num2 相等的元素放到 Set 当中即可。

代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        Set set = new HashSet();

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]){
                    set.add(nums1[i]);
                    break;
                }
            }
        }

        Iterator iterator = set.iterator();
        
        int[] result = new int[set.size()];
        int i = 0;
        
        while (iterator.hasNext()){
            int next = (int)iterator.next();
            result[i] = next;
            i++;
        }
        
        return result;
    }
}

提交结果

代码分析

不考虑集合框架底层原理的话：

• 时间复杂度：O(nm)
• 空间复杂度：O(k)，k 为 n 和 m 中 length 小的那个

[法2] 去掉双层 for 循环

思路

直接用两个 HashSet，然后利用内置方法 contains() 来判断重复元素，这样更快。

代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        Set set1 = new HashSet();
        Set set2 = new HashSet();

        for (int num : nums1){
            set1.add(num);
        }
        
        for (int num: nums2){
            if (set1.contains(num)){
                set2.add(num);
            }
        }
        
        int[] result = new int[set2.size()];
        int i = 0;

        Iterator iterator = set2.iterator();

        while (iterator.hasNext()){
            result[i] = (int)iterator.next();
            i++;
        }
        
        return result;
    }
}

提交结果

代码分析

不考虑集合框架底层原理的话：

• 时间复杂度：O(k)
• 空间复杂度：O(k)