本文共 2513 字，大约阅读时间需要 8 分钟。
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]
说明：
进阶:
解法一：效率比较低
class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ res = [] for k in nums1: if k in nums2: res.append(k) nums2.remove(k) return res
解法二：先排序，因为两只数组已经按升序排好序，所以当 i 指针和 j 指针指向的数值相等时，放入新list；如果 i 指针指向的数 < j 指针指向的数，那么 i 指针前进；如果 i 指针指向的数 > j 指针指向的数，那么 j 指针前进; 错位遍历。
class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ ans = [] nums1.sort() nums2.sort() i = j = 0 while i
以下是Java版本：
这道题是之前那道的拓展，不同之处在于这道题允许我们返回重复的数字，而且是尽可能多的返回，之前那道题是说有重复的数字只返回一个就行。那么这道题我们用哈希表来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组，如果当前字符在哈希表中的个数大于0，则将此字符加入结果res中，然后哈希表的对应值自减1
题意： 求两个数组的交集（包括重复出现的元素）。
思路： 1.遍历数组nums1，将其中的元素放入HashMap<Integer,Integer>中进行统计；
2.新建ArrayList作为存储交集的元素（可重复元素）； 3.遍历数组nums2，如果元素num2在map中出现过，则将其加入到list中，并将其对应的值-1; 4.将list转为数组返回即可。public class Solution { public int[] intersect(int[] nums1, int[] nums2) { Map map = new HashMap (); for(int num1:nums1){ if(!map.containsKey(num1)){ map.put(num1,1); }else{ map.put(num1,map.get(num1) + 1); } } List list = new ArrayList (); for(int num2:nums2){ if(map.containsKey(num2) && map.get(num2) > 0){ list.add(num2); map.put(num2,map.get(num2) - 1); } } int[] res = new int[list.size()]; for(int i = 0;i < list.size();i++){ res[i] = list.get(i); } return res; }} 思路：
承接上题
不同的是，这里可以有重复元素。因此使用List即可。
1. public class Solution { 2. public int[] intersect(int[] nums1, int[] nums2) { 3. 4. List list = new ArrayList (); 5. List interList = new ArrayList (); 6. 7. for(int num:nums1) { 8. list.add(num); 9. } 10. 11. for(int i=0;i
转载地址：http://kvuvi.baihongyu.com/