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

sisterAn · 2020-04-05T14:58:55Z

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

示例 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

finghtingjie · 2020-04-06T01:49:43Z

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

ai977313677 · 2020-04-06T02:19:15Z

用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;
}

zhdxmw · 2020-04-06T03:15:01Z

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
};

liwuhou · 2020-04-06T06:11:13Z

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

Aiyoweioo · 2020-04-06T06:48:26Z

/*找交集*/
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]

sonicwang1989 · 2020-04-06T07:04:55Z

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]

liwuhou · 2020-04-06T07:19:14Z

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]

sonicwang1989 · 2020-04-06T07:25:08Z

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]

改了，没注意去重

uuRRx0 · 2020-04-06T08:21:03Z

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

sisterAn · 2020-04-06T12:47:40Z

解题思路：

filter 过滤
Set 去重

代码实现：

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

leetcode

kizuner-bonely · 2020-04-06T13:48:16Z

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';
}

JerryWen1994 · 2020-04-07T05:37:29Z

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

kizuner-bonely · 2020-04-07T08:33:15Z

@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';
}

lyllovelemon · 2020-04-08T08:07:35Z

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

2601178727 · 2020-04-09T06:58:18Z

Array.from(new Set(nums1)).filter(item => nums2.indexOf(item) > -1)

xszi · 2020-04-12T12:53:56Z

用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;
}

没去重哦

qingfengmy · 2020-04-21T09:55:08Z

能不能把时间和空间复杂度都写上去

msisliao · 2020-04-26T03:24:57Z

let intersection = nums1.filter(item => { if(nums2.includes(item)){ return item } })

zero9527 · 2020-04-28T03:01:52Z

/**
 * 查找 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]

consoles · 2020-05-02T08:03:53Z

用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之后将其删除即可

huangzhuangjia · 2020-05-05T07:41:27Z

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;
};

ruochuan12 · 2020-05-14T06:47:46Z

// 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)

Been101 · 2020-07-11T10:25:06Z

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
}

baebae996 · 2020-12-03T01:29:49Z

用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数组包含重复元素噢

azl397985856 · 2021-03-03T04:56:12Z

题目地址(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 啦。

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

JohnApache · 2021-04-26T02:33:09Z

用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;
};

ninenan · 2021-08-18T10:27:43Z

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;
  }, []);
}

RyanMeg123 · 2022-05-23T11:37:39Z

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

RainyNight9 · 2023-09-27T02:21:28Z

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
};

lyllovelemon · 2023-09-27T02:21:54Z

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

sisterAn changed the title ~~leetcode：给定两个数组，编写一个函数来计算它们的交集~~ leetcode349：给定两个数组，编写一个函数来计算它们的交集 Apr 8, 2020

sisterAn added LeetCode 腾讯 labels May 5, 2020

sisterAn mentioned this issue May 25, 2020

前端进阶算法8：头条正在面的哈希表问题 #49

Open

qianbaiduhai mentioned this issue Oct 26, 2020

编程题：以下输出顺序多少 (setTimeout 与 promise 顺序) #120

Open

sisterAn changed the title ~~leetcode349：给定两个数组，编写一个函数来计算它们的交集~~ 腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集 Jan 31, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

sisterAn commented Apr 5, 2020 •

edited

Loading

finghtingjie commented Apr 6, 2020 •

edited

Loading

ai977313677 commented Apr 6, 2020

zhdxmw commented Apr 6, 2020 •

edited

Loading

liwuhou commented Apr 6, 2020 •

edited

Loading

Aiyoweioo commented Apr 6, 2020 •

edited by sisterAn

Loading

sonicwang1989 commented Apr 6, 2020 •

edited

Loading

liwuhou commented Apr 6, 2020

sonicwang1989 commented Apr 6, 2020

uuRRx0 commented Apr 6, 2020

sisterAn commented Apr 6, 2020 •

edited

Loading

kizuner-bonely commented Apr 6, 2020

JerryWen1994 commented Apr 7, 2020

kizuner-bonely commented Apr 7, 2020

lyllovelemon commented Apr 8, 2020

2601178727 commented Apr 9, 2020

xszi commented Apr 12, 2020

qingfengmy commented Apr 21, 2020

msisliao commented Apr 26, 2020

zero9527 commented Apr 28, 2020 •

edited

Loading

consoles commented May 2, 2020

huangzhuangjia commented May 5, 2020

ruochuan12 commented May 14, 2020 •

edited

Loading

Been101 commented Jul 11, 2020

baebae996 commented Dec 3, 2020

azl397985856 commented Mar 3, 2021

JohnApache commented Apr 26, 2021

ninenan commented Aug 18, 2021

RyanMeg123 commented May 23, 2022

RainyNight9 commented Sep 27, 2023

lyllovelemon commented Sep 27, 2023 via email

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

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

Comments

sisterAn commented Apr 5, 2020 • edited Loading

finghtingjie commented Apr 6, 2020 • edited Loading

ai977313677 commented Apr 6, 2020

zhdxmw commented Apr 6, 2020 • edited Loading

liwuhou commented Apr 6, 2020 • edited Loading

Aiyoweioo commented Apr 6, 2020 • edited by sisterAn Loading

sonicwang1989 commented Apr 6, 2020 • edited Loading

liwuhou commented Apr 6, 2020

sonicwang1989 commented Apr 6, 2020

uuRRx0 commented Apr 6, 2020

sisterAn commented Apr 6, 2020 • edited Loading

kizuner-bonely commented Apr 6, 2020

JerryWen1994 commented Apr 7, 2020

kizuner-bonely commented Apr 7, 2020

lyllovelemon commented Apr 8, 2020

2601178727 commented Apr 9, 2020

xszi commented Apr 12, 2020

qingfengmy commented Apr 21, 2020

msisliao commented Apr 26, 2020

zero9527 commented Apr 28, 2020 • edited Loading

consoles commented May 2, 2020

huangzhuangjia commented May 5, 2020

ruochuan12 commented May 14, 2020 • edited Loading

Been101 commented Jul 11, 2020

baebae996 commented Dec 3, 2020

azl397985856 commented Mar 3, 2021

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

题目描述

前置知识

公司

思路

关键点解析

代码

JohnApache commented Apr 26, 2021

ninenan commented Aug 18, 2021

RyanMeg123 commented May 23, 2022

RainyNight9 commented Sep 27, 2023

lyllovelemon commented Sep 27, 2023 via email

sisterAn commented Apr 5, 2020 •

edited

Loading

finghtingjie commented Apr 6, 2020 •

edited

Loading

zhdxmw commented Apr 6, 2020 •

edited

Loading

liwuhou commented Apr 6, 2020 •

edited

Loading

Aiyoweioo commented Apr 6, 2020 •

edited by sisterAn

Loading

sonicwang1989 commented Apr 6, 2020 •

edited

Loading

sisterAn commented Apr 6, 2020 •

edited

Loading

zero9527 commented Apr 28, 2020 •

edited

Loading

ruochuan12 commented May 14, 2020 •

edited

Loading