350. Intersection of Two Arrays II

# Easy

Two methods: (assume len(nums1) < len(nums2))

1. 暴力解法. Ask each element in nums1 whether in nums2, if yes, then remove this element from both lists and add to result list.

2. Hash map. Build a dictinonary <numss[i], n>, means nums1[i] appears n times in nums1. Use this dictionary to traversal all elements in nums2.

Python(I)

Time complexity = $O(min(n, m))$if if x in nums2 only consume $O(1)$ ; space complexity = $O(min(n, m))$

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) < len(nums2):
            return self.helper(nums1, nums2)
        else:
            return self.helper(nums2, nums1)
        
    def helper(self, nums1, nums2):
        result = []
        while len(nums1) != 0:
            x = nums1.pop()
            if x in nums2:
                result.append(x)
                nums2.remove(x)
            
        return result

Second Tab