参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！

349. 两个数组的交集

力扣题目链接

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

说明： 输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

思路

关于本题，我录制了讲解视频：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集，看视频配合题解，事半功倍。

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序

这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。

那么用数组来做哈希表也是不错的选择，例如242. 有效的字母异位词

但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

思路如图所示：

C++代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

拓展

那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧这个耗时，在数据量大的情况，差距是很明显的。

后记

本题后面力扣改了题目描述和后台测试数据，增添了数值范围：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

所以就可以使用数组来做哈希表了，因为数组都是 1000以内的。

对应C++代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话，result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

其他语言版本

Java：

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        //将结果几何转为数组
        return resSet.stream().mapToInt(x -> x).toArray();
    }
}

Python3：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))    # 两个数组先变成集合，求交集后还原为数组

Go：

func intersection(nums1 []int, nums2 []int) []int {
    m := make(map[int]int)
    for _, v := range nums1 {
        m[v] = 1
    }
    var res []int
    // 利用count>0，实现重复值只拿一次放入返回结果中
    for _, v := range nums2 {
        if count, ok := m[v]; ok && count > 0 {
            res = append(res, v)
            m[v]--
        }
    }
    return res
}

//优化版，利用set，减少count统计
func intersection(nums1 []int, nums2 []int) []int {
    set:=make(map[int]struct{},0)
    res:=make([]int,0)
    for _,v:=range nums1{
        if _,ok:=set[v];!ok{
            set[v]=struct{}{}
        }
    }
    for _,v:=range nums2{
        //如果存在于上一个数组中，则加入结果集，并清空该set值
        if _,ok:=set[v];ok{
            res=append(res,v)
            delete(set, v)
        }
    }
    return res
}

javaScript:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    // 根据数组大小交换操作的数组
    if(nums1.length < nums2.length) {
        const _ = nums1;
        nums1 = nums2;
        nums2 = _;
    }
    const nums1Set = new Set(nums1);
    const resSet = new Set();
    // for(const n of nums2) {
    //     nums1Set.has(n) && resSet.add(n);
    // }
    // 循环 比 迭代器快
    for(let i = nums2.length - 1; i >= 0; i--) {
        nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
    }
    return Array.from(resSet);
};

TypeScript:

版本一（正常解法）：

function intersection(nums1: number[], nums2: number[]): number[] {
    let resSet: Set<number> = new Set(),
        nums1Set: Set<number> = new Set(nums1);
    for (let i of nums2) {
        if (nums1Set.has(i)) {
            resSet.add(i);
        }
    }
    return Array.from(resSet);
};

版本二（秀操作）：

function intersection(nums1: number[], nums2: number[]): number[] {
    return Array.from(new Set(nums1.filter(i => nums2.includes(i))))
};

Swift：

func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    var set1 = Set<Int>()
    var set2 = Set<Int>()
    for num in nums1 {
        set1.insert(num)
    }
    for num in nums2 {
        if set1.contains(num) {
            set2.insert(num)
        }
    }
    return Array(set2)
}

PHP:

class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        if (count($nums1) == 0 || count($nums2) == 0) {
            return [];
        }
        $counts = [];
        $res = [];
        foreach ($nums1 as $num) {
            $counts[$num] = 1;
        }
        foreach ($nums2 as $num) {
            if (isset($counts[$num])) {
                $res[] = $num;
            }
            unset($counts[$num]);
        }
        
        return $res;
    }
}

Rust:

use std::collections::HashSet;
impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut resultSet: HashSet<i32> = HashSet::with_capacity(1000);
        let nums1Set: HashSet<i32> = nums1.into_iter().collect();
        
        for num in nums2.iter() {
            if nums1Set.contains(num) {
                resultSet.insert(*num);
            }          
        }
        
        let ret: Vec<i32> = resultSet.into_iter().collect();
        ret
    }
}

C:

int* intersection1(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){

    int nums1Cnt[1000] = {0};
    int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;
    int * result = (int *) calloc(lessSize, sizeof(int));
    int resultIndex = 0;
    int* tempNums;
    
    int i;

    /* Calculate the number's counts for nums1 array */
    for(i = 0; i < nums1Size; i ++) {
        nums1Cnt[nums1[i]]++;
    }

    /* Check if the value in nums2 is existing in nums1 count array */
    for(i = 0; i < nums2Size; i ++) {
        if(nums1Cnt[nums2[i]] > 0) {
            result[resultIndex] = nums2[i];
            resultIndex ++;
            /* Clear this count to avoid duplicated value */
            nums1Cnt[nums2[i]] = 0;
        }
    }
    * returnSize = resultIndex;
    return result;
}

Scala:

正常解法:

object Solution {
  def intersection(nums1: Array[Int], nums2: Array[Int]): Array[Int] = {
    // 导入mutable
    import scala.collection.mutable
    // 临时Set，用于记录数组1出现的每个元素
    val tmpSet: mutable.HashSet[Int] = new mutable.HashSet[Int]()
    // 结果Set，存储最终结果
    val resSet: mutable.HashSet[Int] = new mutable.HashSet[Int]()
    // 遍历nums1，把每个元素添加到tmpSet
    nums1.foreach(tmpSet.add(_))
    // 遍历nums2，如果在tmpSet存在就添加到resSet
    nums2.foreach(elem => {
      if (tmpSet.contains(elem)) {
        resSet.add(elem)
      }
    })
    // 将结果转换为Array返回，return可以省略
    resSet.toArray
  }
}

骚操作1:

object Solution {
  def intersection(nums1: Array[Int], nums2: Array[Int]): Array[Int] = {
    // 先转为Set，然后取交集，最后转换为Array
    (nums1.toSet).intersect(nums2.toSet).toArray
  }
}

骚操作2:

object Solution {
  def intersection(nums1: Array[Int], nums2: Array[Int]): Array[Int] = {
    // distinct去重，然后取交集
    (nums1.distinct).intersect(nums2.distinct)
  }
}

C#:

 public int[] Intersection(int[] nums1, int[] nums2) {
    if(nums1==null||nums1.Length==0||nums2==null||nums1.Length==0)
    	return new int[0]; //注意数组条件
    HashSet<int> one = Insert(nums1);
    HashSet<int> two = Insert(nums2);
    one.IntersectWith(two);
    return one.ToArray();
	}
 public HashSet<int> Insert(int[] nums){
    HashSet<int> one = new HashSet<int>();
    foreach(int num in nums){
    	one.Add(num);         
    	}
        return one;
	}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0349.两个数组的交集.md

0349.两个数组的交集.md

349. 两个数组的交集

思路

拓展

后记

其他语言版本

相关题目

Files

0349.两个数组的交集.md

Latest commit

History

0349.两个数组的交集.md

File metadata and controls

349. 两个数组的交集

思路

拓展

后记

其他语言版本

相关题目