Method 1: double pointer comparison

When I saw this problem, I remembered an intersection of linked lists I had done in school OJ. Essentially, the two problems were solved in the same way

Ideas:

1. We sort the arrays and set two Pointers to the heads of each array
2. It then compares whether the data to which the pointer points is equal, if so, it stores that data into the answer RES array, and finally moves both Pointers back one bit
3. If the data is not equal, the pointer with the smaller data is moved backward, and then 2 or 3 steps are repeated until one pointer is out of range

var intersect = function (nums1, nums2) {
    nums1=nums1.sort((a,b) = >a-b)
    nums2=nums2.sort((a,b) = >a-b)
    let i=0,j=0
    let res=[]
    while(i<nums1.length&&j<nums2.length){
        if(nums1[i]==nums2[j]){
            res.push(nums1[i])
            i++
            j++
        }
        else if(nums1[i]<nums2[j]){
            i++
        }
        else if(nums1[i]>nums2[j]){
            j++
        }
    }
    return res
};
Copy the code

Time complexity: sort is O(mlogm+nlogn)

Space complexity: O(min(m,n))

Method two: hash table

Ideas:

1. Creates a hash table that stores the number of occurrences of each number in a specified array
2. Iterate over the second array. If the number is present in the hash table and the degree is not zero, add it to the array of answer res and subtract one from the number of occurrences in the hash table

let hashmap = {}
let res=[]
for (let i = 0; i < nums1.length; i++) {
     if(! hashmap.hasOwnProperty(nums1[i])) { hashmap[nums1[i]] =1
     }
     else{
                hashmap[nums1[i]]++
     }
}
for(let i=0; i<nums2.length; i++){if(hashmap.hasOwnProperty(nums2[i]) && hashmap[nums2[i]]>0){
                res.push(nums2[i])
                hashmap[nums2[i]]--
     }
}    
return res
Copy the code

If the length of two arrays is very different, nums1 is much larger than NUMs2, how can we optimize

In fact, the solution is to create hash tables for smaller arrays, reducing space complexity

if(nums1.length>nums2.length) return  intersect(nums2,nums1)
Copy the code

Time complexity: O(m+ N)

Space complexity: O(min(m,n))