349. Intersection of Two Arrays

Version #1 HashSet
Iterate through the shorter array and add every number into a hashset.
Iterate through the other array, if any number is found in the previous hashset, we should add it to our result set.
Time: O(m + n)  Space: O(min(m, n))
30.76%

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        //Assume that nums1 is shorter than nums2
        if (nums1.length > nums2.length) return intersection(nums2, nums1);
        Set<Integer> hash = new HashSet<>();
        Set<Integer> resultSet = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            hash.add(nums1[i]);
        }
        for (int j = 0; j < nums2.length; j++) {
            if (hash.contains(nums2[j])) resultSet.add(nums2[j]);
        }
        int[] result = new int[resultSet.size()];
        int index = 0;
        for (Integer n : resultSet) {
            result[index++] = n;
        }
        return result;
    }
}

Version #2 Sort and Merge
Firstly, sort the input arrays. Use two pointers to scan the two arrays simultaneously to find equal numbers.
If there's any duplicates, we choose the 1st occurrence of that number as the representative of the result.
Time: O(mlogm + nlogn) Space: O(1)
99.16%

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int p1 = 0, p2 = 0;
        int[] result = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] < nums2[p2]) p1++;
            else if (nums1[p1] > nums2[p2]) p2++;
            else {
                //System.out.println("p1:" + nums1[p1] + " p2:" + nums2[p2]);
                if (index == 0 || nums1[p1] != result[index - 1]) {
                    result[index++] =  nums1[p1];
                }
                p1++;
                p2++;
            }
        }
        result = Arrays.copyOf(result, index);
        return result;
    }
}

Version #3 Binary Search
15.63%

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        //Assume that nums1 is shorter
        if (nums1.length > nums2.length) return intersection(nums2, nums1);
        Arrays.sort(nums1);
        Set<Integer> resultSet = new HashSet<>();
        for (int i = 0; i < nums2.length; i++) {
            if(binarySearch(nums2[i], nums1)) resultSet.add(nums2[i]);
        }
        int[] result = new int[resultSet.size()];
        int index = 0;
        for (int n : resultSet) {
            result[index++] = n;
        }
        return result;
    }
    private boolean binarySearch(int target, int[] array) {
        int start = 0;
        int end = array.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (array[mid] == target) return true;
            if (array[mid] > target) end = mid;
            else start = mid;
        }
        if (array[start] == target || array[end] == target) return true;
        return false;
    }
}