349. Intersection of Two Arrays

349. Intersection of Two Arrays

Question

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]

Thinking:

• Method 1:HashSet
  • 通过第一个HashSet来存储重复。
  • 第二个set去取重。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        for(int num : nums1)
            set.add(num);
        for(int num : nums2)
            if(set.contains(num))
                res.add(num);
        int[] arr = new int[res.size()];
        int i = 0;
        for(Integer num : res)
            arr[i++] = num;
        return arr;
    }
}

• Method 2: 双指针

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index1 = 0, index2 = 0;
        Set<Integer> set = new HashSet<>();
        while(index1 < nums1.length && index2 < nums2.length){
            int a = nums1[index1++], b = nums2[index2++];
            System.out.println(a + " " +b);
            if(a == b){
                set.add(a);
            }else if(a < b){
                index2--;
            }else
                index1--;
        }
        int[] res = new int[set.size()];
        int i = 0;
        for(int num : set)
            res[i++] = num;
        return res;
    }
}