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

[sisterAn]

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

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

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

[ai977313677]

用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]

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]

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

[Aiyoweioo]

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

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]

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]

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]

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

[sisterAn]

解题思路：

• filter 过滤
• Set 去重

代码实现：

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

leetcode

[kizuner-bonely]

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]

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

[kizuner-bonely]

@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]

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

[2601178727]

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

[xszi]

用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]

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

[msisliao]

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

[zero9527]

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

用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]

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]

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

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]

用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]

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

用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]

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]

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

[RainyNight9]

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]

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