---
# System prepended metadata

title: Leetcode 349. Intersection of Two Arrays
tags: [Set, Bit Manipulation, Leetcode, Binary Search]

---

## 題解

### 使用 HashSet Intersection

```python=
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1).intersection(nums2))
```

### 使用 HashSet 和 Bit Manipulation

```python=
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return set(nums1) & set(nums2)
```

### 使用 HashSet 和 Binary Search

```python=
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # O(n2logn)
        n1 = len(nums1)
        n2 = len(nums2)

        def binary_search(nums: List[int], target: int):
            n = len(nums)
            left, right = 0, n - 1

            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
            return -1
        
        if n1 < n2:
            target_arr = nums2
            search_arr = nums1
        else:
            target_arr = nums1
            search_arr = nums2
        
        search_arr = sorted(search_arr) # 小的做 sorted
        output = []
        for target in set(target_arr): # 大的做迴圈
            if binary_search(search_arr,target) >= 0: # 找到就加入 output 中
                output.append(target)

        return output
```