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)