FB
交集見LeetCode349
第一種解法：Time: O(nlogn) Space:O(N), Two pointers + hashSet 要求返回的int[] 不能有duplicate應(yīng)該是能反應(yīng)過來要用hashset的。

class Solution {
    //求兩數(shù)組交集
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0; 
        int j = 0;
        int indx = 0;
        while (i < nums1.length && j < nums2.length){
            if (nums1[i] == nums2[j]){
                set.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]){
                i++;
            } else {
                j++;
            }
        }
        int[] res = new int[set.size()];
        int index = 0;
        for (int in : set){
            res[index++] = in;
        }
        return res;
    }
}

第二種解法time:O(N), space:O(N)

class Solution {
    //求兩數(shù)組交集
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> intersect = new HashSet<>();
        for (int i : nums1){
            set1.add(i);
        }
        for (int i : nums2){
            if (set1.contains(i)){
                intersect.add(i);
            }
        }
        int[] res = new int[intersect.size()];
        int index = 0;
        for (int i : intersect){
            res[index++] = i;
        }
        return res;
    }
}

面試follow up：根據(jù)input size不同寫更efficient的算法，最后讓寫一個binay search. 比如nums1很小，nums2很大，那么我們就可以把num1里面的每個元素拿到nums2里面去做二分查找，找到就加到intersect set里面。
第三種方法：binary search Time:O(nlogn)

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums2);
        for (Integer num : nums1) {
            if (binarySearch(nums2, num)) {
                set.add(num);
            }
        }
        int i = 0;
        int[] result = new int[set.size()];
        for (Integer num : set) {
            result[i++] = num;
        }
        return result;
    }
    
    public boolean binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

求差集：

/*
 *給兩個sorted數(shù)組A和B，求B中不包含A的數(shù)字，例如A=（1）， B= （1，2，3），返回(2,3)
*/

public int[] findNumsInBNotInA(int[] A, int[] B){
    List<Integer> res = new ArrayList<>();
    for (int intInB : B){
        if (!res.contains(intInB)){
            res.add(intInB);
        }
    }
    for (int intInA : A){
        if (res.contains(intInA)){
            res.remove(intInA);
        }
    }
    int[] arr = {};
    return res.toArray(arr);
}