# Intersection of Two Arrays II

### 描述​

Given two arrays, write a function to compute their intersection.

Example 1:

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

Example 2:

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

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

### 代码​

#### 排序​

// Intersection of Two Arrays II// Sort// Time Complexity: O(mlogm+nlogn)// Space Complexity:  from O(logm+logn) to O(n+m), depending// on the implementation of the sorting algorithm.class Solution {    public int[] intersect(int[] nums1, int[] nums2) {        Arrays.sort(nums1);        Arrays.sort(nums2);        int i = 0, j = 0, k = 0;        while (i < nums1.length && j < nums2.length) {            if (nums1[i] < nums2[j]) {                ++i;            } else if (nums1[i] > nums2[j]) {                ++j;            } else {                nums1[k++] = nums1[i++];                ++j;            }        }        return Arrays.copyOfRange(nums1, 0, k);    }}

#### HashMap​

// Intersection of Two Arrays II// HashMap// Time Complexity: O(m + n), Space Complexity:  O(min(m + n))class Solution {    public int[] intersect(int[] nums1, int[] nums2) {        if (nums1.length > nums2.length) return intersect(nums2, nums1);        Map<Integer, Integer> m = new HashMap<>();        for (int x : nums1) {            m.merge(x, 1, Integer::sum);        }        int k = 0;        for (int x : nums2) {            int count = m.getOrDefault(x, 0);            if (count > 0) {                nums1[k++] = x;                m.put(x, count - 1);            }        }        return Arrays.copyOfRange(nums1, 0, k);    }}