> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/intersection-of-two-arrays/intersection-of-two-arrays-ii.md).

# 350. Intersection of Two Arrays II

https\://leetcode.com/problems/intersection-of-two-arrays-ii/description/

> Given two arrays, write a function to compute their intersection.
>
> Example:
>
> Given nums1 = \[1, 2, 2, 1], nums2 = \[2, 2], return \[2, 2].
>
> Note:
>
> Each element in the result should appear as many times as it shows in both arrays.
>
> The result can be in any order.
>
> Follow up:
>
> 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?

## Thoughts

找两个数组的交集，允许重复元素。用freq map，nums1 -1，nums2 +1，当结果小于等于0时是交集元素。

```
/*
 * @lc app=leetcode id=350 lang=cpp
 *
 * [350] Intersection of Two Arrays II
 */

// @lc code=start
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> freqs;
        for (const auto num : nums1) {
            if (!freqs.count(num)) freqs[num] = 0;
            --freqs[num];
        } 
        vector<int> res;
        for (const auto num : nums2) {
            if (!freqs.count(num)) continue;
            ++freqs[num];
            if (freqs[num] <= 0) res.push_back(num); 
        }
        return res;
    }
};
// @lc code=end


```

可以用map记录频率. 这里假设排好序了, 和I的解法一样.

如果一个特别小另一个特别大, 可以把小的放进hash map, 然后每次从大的读入小的那么多. 或者对大的排序(external sort), 然后两指针或者二分法.

<https://discuss.leetcode.com/topic/45992/solution-to-3rd-follow-up-question/3?page=1>

参考follow up的答案.

## Code

```
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> res = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        for (int i = 0, j = 0; i < nums1.length && j < nums2.length;) {
            if (nums1[i] < nums2[j]) {
                i++;    
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                res.add(nums1[i]);
                i++;
                j++;
            }
        }

        int[] r = new int[res.size()];
       for(int i = 0; i < res.size(); i++) {
           r[i] = res.get(i);
       }

       return r;
    }
}
```

## Analysis

取决于是否排好序.