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

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:
Each element in the result must be unique.
The result can be in any order.

Method 1: 把nums1的数字都放hashset中，看nums2中有没有和hashset中一样的数，一样的存到另一个hashset中

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) return null;

        //把num1的值都放到set1中
        HashSet<Integer> set1 = new HashSet<>();
        for(int i = 0; i < nums1.length; i++) {
            set1.add(nums1[i]);
        }

        //当set1中包含nums2中的数且setRes中不包含时，将此数放入setRes中
        HashSet<Integer> setRes = new HashSet<>();
        for(int i = 0; i < nums2.length; i++) {
            if(set1.contains(nums2[i]) && !setRes.contains(nums2[i])) setRes.add(nums2[i]);
        }

        //把set转换成array
        int size = setRes.size();
        int[] res = new int[size];
        int index = 0;
        for(Integer num: setRes) {
            res[index] = num;
            index++;
        }

        return res;
    }
}


Method 2: sort first, then merge

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) return null;

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int[] temp = new int[nums1.length];
        int i = 0;
        int j = 0;
        int index = 0;

        while(i < nums1.length && j < nums2.length) {
            if(nums1[i] == nums2[j]) {
                if(index == 0 || temp[index - 1] != nums1[i]) {
                    temp[index] = nums1[i];
                    index++;
                }
                i++;
                j++;
            } else if(nums1[i] > nums2[j]) {
                j++;
            } else i++;

        }

        int[] res = new int[index];
        for(int k = 0; k < index; k++) {
            res[k] = temp[k];
        }

        return res;
    }
}



Method 3:先把nums1排序，用辅助方法binarysearch看nums1中是否包含nums2中的每一个数

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) return null;

        Arrays.sort(nums1);

        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < nums2.length; i++) {
            if(binarySearch(nums1, nums2[i]) && !set.contains(nums2[i])) {
                set.add(nums2[i]);
            }
        }

        int size = set.size();
        int[] res = new int[size];
        int index = 0;
        for(Integer num: set) {
            res[index++] = num;
        }

        return res;
    }

    private boolean binarySearch(int[] nums, int target) {
        if(nums == null || nums.length == 0) return false;

        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if(nums[mid] == target) return true;
            else if(nums[mid] < target) start = mid;
            else end = mid;
        }
        if(nums[start] == target || nums[end] == target) return true;
        return false;
    }
}