腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集

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

示例 1:

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

示例 2:

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

说明:

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

附leetcode地址：leetcode

const fn = (n1,n2)=>[...new Set(n1.filter(i => n2.includes(i)))]; console.log(fn([1,2,2,1],[2,2]))

用Map是O(n)的时间

var intersection = function(nums1, nums2) {
    const map = {}, ans = [];
    nums1.forEach(element => {
        map[element] = true;
    });
    nums2.forEach(element => {
        if (map[element]) {
            ans.push(element);
        }
    });
    return ans;
}

var intersection = function(nums1, nums2) {
    let map1 = new Set(nums1);
    let map2 = new Set(nums2);
    let res = []
    map1.forEach((item) => {
        if(map2.has(item)){
             res.push(item)
        }
       
    })
    return res
};

const getIntersection = (nums1, nums2) => {
    return Array.from(new Set(nums1.filter(item => !!~nums2.indexOf(item))));
}

/*找交集*/
function intersection(arr1, arr2){
 var hash = {}, _intersection = []
  for(let ele of arr1){
    if(!hash.hasOwnProperty(ele)){
      hash[ele] = true
    }
  }
  for(let ele of arr2){
    if(hash[ele]){
      var flag = false // NaN标志 
      if(_intersection.indexOf(ele) === -1){
        if(ele !== ele){
          if(!flag){
            flag = true
            _intersection.push(ele)
          }
        }else{
          _intersection.push(ele)
        }
      }  
    }
  }
  return _intersection
}
console.log(intersection([1,2,2,1], [2,2])) // [2]
console.log(intersection([4,9,5], [9,4,9,8,4])) // [9,4]
console.log(intersection([4,9,5,NaN], [9,4,9,8,4,NaN])) // [9,4,NaN]

/*找并集*/
function union(arr1,arr2){
  return Array.from(new Set([...arr1, ...arr2]))
}
console.log(union([1,2,2,1], [2,2])) // [1,2]
console.log(union([4,9,5], [9,4,9,8,4])) // [4,9,5,8]
console.log(union([4,9,5,NaN], [9,4,9,8,4,NaN])) // [4,9,5,NaN,8]

/*找差集*/
function difference(arr1, arr2){
  var set1 = new Set(arr1)
  var set2 = new Set(arr2)
  for(let ele of set1){
    if(set2.has(ele)){
      set2.delete(ele)
    }
  }
  return Array.from(set2)
}
console.log(difference([1,2,2,1], [2,2])) // []
console.log(difference([4,9,5], [9,4,9,8,4])) // [8]
console.log(difference([4,9,5,NaN], [9,4,9,8,4,NaN])) // [8]

var fn = (nums1, nums2) => {
    var small = nums1, big = nums2;
    if (nums1.length > nums2.length) {
        small = nums2;
        big = nums1;
    }

    return Array.from(new Set(small.filter(t => big.indexOf(t) > -1)));
};

console.log(fn([1, 2, 2, 1], [2, 2])) // [2]
console.log(fn([4,9,5], [9,4,9,8,4])) // [4,9]

var fn = (nums1, nums2) => {
    var small = nums1, big = nums2;
    if (nums1.length > nums2.length) {
        small = nums2;
        big = nums1;
    }

    return small.filter(t => big.indexOf(t) > -1);
};

fn([1, 2, 3, 4], [2, 6])

这个好像不满足

fn([1,2,3,4], [2,2]) // [2,2]

var fn = (nums1, nums2) => {
    var small = nums1, big = nums2;
    if (nums1.length > nums2.length) {
        small = nums2;
        big = nums1;
    }

    return small.filter(t => big.indexOf(t) > -1);
};

fn([1, 2, 3, 4], [2, 6])

这个好像不满足

fn([1,2,3,4], [2,2]) // [2,2]

改了，没注意去重

function getIntersection(arr1, arr2) {
        var arr = [];
        arr1.forEach(function(elem) {
            arr2.includes(elem) && !arr.includes(elem) && arr.push(elem);
        })
        return arr;
    }

解题思路：

filter 过滤
Set 去重

代码实现：

const intersection = function(nums1, nums2) {
    return [...new Set(nums1.filter((item)=>nums2.includes(item)))]
};

leetcode

function intersection(arr1, arr2) {
    if( arr1 instanceof Array && arr2 instanceof Array ){
        return Array.from(new Set(arr1.filter(item=>new Set(arr2).has(item))));
    }
    throw 'What I need are two arrays';
}

@WeCheung 你这filter里面，每一次都要new Set一遍，虽然代码简写了，但浪费了很多资源

@597796340 多谢提醒

function intersection(arr1, arr2) {
    if( arr1 instanceof Array && arr2 instanceof Array ){
        const set = new Set(arr2);
        return Array.from(new Set(arr1.filter(item=>set.has(item))));
    }
    throw 'What I need are two arrays';
}

function combineArr(arr1,arr2) {
  let res=arr1.filter((item)=> arr2.includes(item))
    return new Set(res)
}

/**
 * 查找 arr1与arr2之间的交集
 * @param {*} arr1
 * @param {*} arr2
 */
const sameItem = (arr1, arr2) => arr1.filter((i) => arr2.includes(i));

const arr1 = [1, 2, 3, 4, 2, 1];
const arr2 = [3, 4, 5, 6, 3, 4];
console.log(sameItem(arr1, arr2)); // [3, 4]

用Map是O(n)的时间

var intersection = function(nums1, nums2) {
    const map = {}, ans = [];
    nums1.forEach(element => {
        map[element] = true;
    });
    nums2.forEach(element => {
        if (map[element]) {
            ans.push(element);
        }
    });
    return ans;
}

没去重哦

去重很简单，第二个for循环判断map中存在元素之后，ans的push之后将其删除即可

var intersection = function(nums1, nums2) {
   var result = [];
   var set1 = new Set([...nums1]);
   var set2 = new Set([...nums2]);
   for (var i of set2) {
     if (set1.has(i)) {
        result.push(i);
     }
   }
   return result;
};

// set 的方案
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    var result = [];
    var smallerSet = new Set(nums1);
    var biggerSet = new Set(nums2);
    if(biggerSet.size < smallerSet.size){
        var temp = smallerSet;
        smallerSet = biggerSet;
        biggerSet = temp;
    }
    smallerSet.forEach((item) => {
        if(biggerSet.has(item)){
            result.push(item);
        }
    });
    return result;
};

Accepted

60/60 cases passed (72 ms)
Your runtime beats 60.86 % of javascript submissions
Your memory usage beats 83.33 % of javascript submissions (34.1 MB)

var intersection = function (nums1, nums2) {
  const map = {},
    ans = []
  nums1.forEach((element) => {
    if (!map[element]) map[element] = 1
  })
  nums2.forEach((element) => {
    if (map[element]) {
      map[element]++
      if (map[element] == 2) {
        ans.push(element)
      }
    }
  })
  return ans
}

用Map是O(n)的时间

var intersection = function(nums1, nums2) {
    const map = {}, ans = [];
    nums1.forEach(element => {
        map[element] = true;
    });
    nums2.forEach(element => {
        if (map[element]) {
            ans.push(element);
        }
    });
    return ans;
}

这样的写法会导致最终的ans数组包含重复元素噢

题目地址(349. 两个数组的交集)

https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目描述

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

 

示例 1：

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

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
 

说明：

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

前置知识

hashtable

公司

阿里
腾讯
百度
字节

思路

先遍历第一个数组，将其存到 hashtable 中，然后遍历第二个数组，如果在 hashtable 中存在就 push 到 ret，然后清空 hashtable，最后返回 ret 即可。

关键点解析

空间换时间

代码

代码支持：JS, Python

Javascript Code:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const visited = {};
  const ret = [];
  for (let i = 0; i < nums1.length; i++) {
    const num = nums1[i];

    visited[num] = num;
  }

  for (let i = 0; i < nums2.length; i++) {
    const num = nums2[i];

    if (visited[num] !== undefined) {
      ret.push(num);
      visited[num] = undefined;
    }
  }

  return ret;
};

Python Code:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        visited, result = {}, []
        for num in nums1:
            visited[num] = num
        for num in nums2:
            if num in visited:
                result.append(num)
                visited.pop(num)
        return result

    # 另一种解法：利用 Python 中的集合进行计算
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return set(nums1) & set(nums2)

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

用Map是O(n)的时间

var intersection = function(nums1, nums2) {
    const map = {}, ans = [];
    nums1.forEach(element => {
        map[element] = true;
    });
    nums2.forEach(element => {
        if (map[element]) {
            ans.push(element);
        }
    });
    return ans;
}

你这个有问题啊，已经推进去的元素，会出现重复的元素，我改了一下，多加一个map 存储已经推进去的元素即可避免重复

const UnionTwoArray = (arr1: number[], arr2: number[]) => {
    const map1: Record<number, boolean> = {};
    const map2: Record<number, boolean> = {};

    const result: number[] = [];
    arr1.forEach(item => {
        map1[item] = true;
    });
    arr2.forEach(item => {
        if (map1[item] && !map2[item]) {
            result.push(item);
            map2[item] = true;
        }
    });
    return result;
};

function intersection(nums1: number[], nums2: number[]): number[] {
  return nums1.reduce((pre: number[], cur: number) => {
    if (nums2.includes(cur) && !pre.includes(cur)) {
      pre.push(cur);
    }
    return pre;
  }, []);
}

function mixed (nums1,nums2) {
    return nums1.reduce((prev,cur) => {
        if (nums2.includes(cur)) {
            prev.push(cur)
        }
        return [...new Set(prev)];
    },[])
}

function intersection(nums1: number[], nums2: number[]): number[] {
  let res = []
  for(let i = 0; i< nums1.length; i++) {
    if(nums2.includes(nums1[i]) && !res.includes(nums1[i])) {
      res.push(nums1[i])
    }
  }
  return res
};

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。

Navigation Menu

Repository navigation

腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集 #6

4 remaining items

题目地址(349. 两个数组的交集)

题目描述

前置知识

公司

思路

关键点解析

代码

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集 #6

Description

Activity

finghtingjie commented on Apr 6, 2020

ai977313677 commented on Apr 6, 2020

zhdxmw commented on Apr 6, 2020

liwuhou commented on Apr 6, 2020

Aiyoweioo commented on Apr 6, 2020

000Sonic commented on Apr 6, 2020

liwuhou commented on Apr 6, 2020

000Sonic commented on Apr 6, 2020

uuRRx0 commented on Apr 6, 2020

sisterAn commented on Apr 6, 2020

hh-cheng commented on Apr 6, 2020

JerryWen1994 commented on Apr 7, 2020

hh-cheng commented on Apr 7, 2020

lyllovelemon commented on Apr 8, 2020

4 remaining items

zero9527 commented on Apr 28, 2020

consoles commented on May 2, 2020

huangzhuangjia commented on May 5, 2020

ruochuan12 commented on May 14, 2020

Been101 commented on Jul 11, 2020

baebae996 commented on Dec 3, 2020

azl397985856 commented on Mar 3, 2021

题目地址(349. 两个数组的交集)

题目描述

前置知识

公司

思路

关键点解析

代码

JohnApache commented on Apr 26, 2021

ninenan commented on Aug 18, 2021

RyanMeg123 commented on May 23, 2022

RainyNight9 commented on Sep 27, 2023

lyllovelemon commented on Sep 27, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions