1. 题目形容

给你两个有序(递增)整数数组 nums1 和 nums2 ，请你以数组模式返回两数组的交加，M为较长数组长度，N为较短数组长度。例如：
给定：nums1 = [1,2,3,4,5,6], nums2 = [1,2,3]
输入:[1,2,3]
这道题常见且并不难，有意思的是解法十分多，在nums1 和 nums2长短不同场景下，筛选最高效的解法

2. 哈希表

这是最容易想到的解法，对较短的数组进行哈希，遍历较长的数组，就能够失去交加

function intersect(nums1, nums2){
    let hash = new Set()//这里用set来代表哈希，他们实质是一样的
    for (let i = 0; i < nums2.length; i++) {
        hash.add(nums2[i])
    }
    for (let i = 0; i < nums1.length; i++) {
        if (hash.has(nums1[i])) {
            ans.push(nums1[i])
        }
    }
    return ans
}

工夫复杂度：O(M+N)<br/>
空间复杂度:对于较短的数组进行了哈希，O(N)

3. 二分查找

思考一个场景,较长的数组十分长，哈希表的解法是线性的，显然没有很好的利用数组有序这个条件，这时二分查找怀才不遇，因为两者长度相差越大，二分效率越高；

function intersect(nums1, nums2){
    //因为是递增，定义一个left,略微缩小下查找范畴
    let left = 0;
    for (let i = 0; i < nums2.length; i++) {
                
        //二分查找
        let index = binarySearch(nums1, nums2[i], left)
        if (index != -1) {
            ans.push(nums2[i])
            left = index + 1
        }
    }    
    return ans
}

function binarySearch(nums, target, left  = 0, right = nums.length - 1){
        //非凡解决 端点的状况 能够减速间断数组的查找
        if(nums[left] == target){
            return left
        }
        if(nums[right] == target){
            return right
        }
    while(left <= right){
        mid =  Math.floor((left + right)/2)
        if (nums[mid] == target) {
            return mid
        }else if(nums[mid] > target){
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    return -1
}

这里重点提一下为什么要优化二分查找的左终点，如果咱们不给定左终点，那么每次二分都是从0 到 len -1二分，而因为数组是有序的，如果曾经在num1中找到了target,那么下一个待查找target的地位必然在上一个target的左边，这样就防止了二分查找每次从0开始,最现实状况下比方nums1 = [1,2,3,4,5,6], nums2 = [4,5,6],第一次查找到4,残余的5,6显然在4的左边，理论只有O(N)次就能够了
工夫复杂度：M为较长数组长度，N为较短数组长度，最差/均匀复杂度O(N*logM)，而且因为咱们优化了二分查找的左终点，最最现实状况下复杂度能够达到O(N)；不是现实状况下，工夫复杂度取决于交加在nums1中的散布状况，交加在nums1中越靠右散布，查找效率越高<br/>
空间复杂度:如果递归数组是援用的话，咱们只应用了常量级变量空间 O(1)

4. 双指针

如果两个数组长度相差不大，那么双指针显然效率更高；

function intersect(nums1, nums2){
    let m = n = 0
    while( m < nums1.length && n < nums2.length ) {
        if (nums1[m] == nums2[n]) {
            ans.push(nums1[m])
            m++
            n++
        }else if (nums1[m] > nums2[n]) {
            n++
        }else{
            m++
        }
    }
    return ans
}

工夫复杂度：M为较长数组长度，N为较短数组长度，最好状况是O(N)，最坏状况是O(M)<br/>
空间复杂度: 只应用了常量级变量空间 O(1)