0%

### 题目描述

Given two integer arrays `nums1` and `nums2`, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

### 例子

#### 例子 1

Input: `nums1 = [1,2,2,1], nums2 = [2,2]`
Output: `[2,2]`

#### 例子 2

Input: `nums1 = [4,9,5], nums2 = [9,4,9,8,4]`
Output: `[4,9]`

What if the given array is already sorted? How would you optimize your algorithm?
What if `nums1`‘s size is small compared to `nums2`‘s size? Which algorithm is better?
What if elements of `nums2` are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

### Constraints

• `1 <= nums1.length, nums2.length <= 1000`
• `0 <= nums1[i], nums2[i] <= 1000`

### 解题思路

[Leetcode]349. Intersection of Two Arrays(C++) 的升级版，要求匹配两数组相同数量的元素，同样可以用二分查找来完成，由于需要匹配相同的数量的元素，所以在二分查找找到目标值之后需要左右扫描找到目标值元素的个数，有几个技巧可以提升速度。

• 左右扫描的找目标值元素的过程同样可以用二分查找来完成，参考：[Leetcode]34. Find First and Last Position of Element in Sorted Array(C++)
• 由于两数组都排序了，所以在每次二分查找结束之后都可以更新下一次查找的左边界（即当前目标值在数组中最后一个位置再加一）
• 其余更简单的方法有哈希表（空间换时间），双指针（也需要预先排序）等等

• 时间复杂度: O(nlog n) -> 排序时间
• 空间复杂度: O(1)

GitHub 代码同步地址： 350.IntersectionOfTwoArraysIi.cpp

GitHub: Leetcode-C++-Solution