350. Intersection of Two Arrays II -- -- Hash Table / Two Pointer

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

参考九章 HashMap + ArrayList 的答案：

http://www.jiuzhang.com/solutions/intersection-of-two-arrays-ii/

public class Solution {

public int[] intersect(int[] nums1, int[] nums2) {

if (nums1 == null || nums2 == null) {

return null;

}

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i = 0; i < nums1.length; i++) {

if (map.containsKey(nums1[i])) {

map.put(nums1[i], map.get(nums1[i]) + 1);

}

else {

map.put(nums1[i], 1);

}

}

List<Integer> resArray = new ArrayList<Integer>();

for (int i = 0; i < nums2.length; i++) {

if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {

resArray.add(nums2[i]);

map.put(nums2[i], map.get(nums2[i]) - 1);

}

// if (map.get(nums2[i]) == 0) {

// map.remove(nums2[i]);

// }

}

int size = resArray.size();

int[] res = new int[size];

int index = 0;

for (Integer num : resArray) {

res[index++] = num;

}

// for (int i = 0; i < size; i++) {

// res[i] = resArray.get(i);

// }

return res;

}

}

**同学总结：用一个map 存其中一个array的元素和出现的次数（key， value）。根据第二个array对这个map遍历， 如果对应元素在map中的次数>0, 作为结果放到ArrayList中，同时此元素次数减一，注意判断条件> 0。 时间 m + n, 空间map 和arrayList， m + n.

结果中可以有重复，两个Array中有几个相同的都出现在结果中。结果用arrayList装， sort两个array用two pointer， 时间 nlogn + n + mlgm + m, 空间ArrayList的size， n + m.