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)