349. Intersection of Two Arrays

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.

//Approach 1: HashSet
//Time: O(n), Space: O(n) 
   public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        
        HashSet<Integer> result = new HashSet<Integer>();
        HashSet<Integer> set = new HashSet<Integer>();
        
        for (int num : nums1) {
            set.add(num);
        }
        
        for (int num : nums2) {
            if (set.contains(num)) {
                result.add(num);
            }
        }
        
        int[] ans = new int[result.size()];
        int i = 0;
        
        for(int ele : result) {//注意：遍历set没法用index assign给array，只能i递增
            ans[i] = ele;
            i++;
        }
        
        return ans;
    }

//Approach 2: Sort + Two pointer
//Time: O(nlogn), Space: O(1)
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        
        HashSet<Integer> result = new HashSet<Integer>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                result.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        int[] ans = new int[result.size()];
        int k = 0;
        
        for(int ele : result) {
            System.out.println(ele);
            ans[k] = ele;
            k++;
        }
        
        return ans;
    }