# 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.

題目是要得到2個陣列的相交，回傳個一個整數陣列。我的解法是

1 先foreach遍尋nums1把nums1的加進hashset s1，因為hashset不重複的特性，nums重複的值就不會存到hashset s1裡。

2 再以nums2遍尋，每個判斷s1.contains(nums2[x])是的話就給hashset s3，因為再進來s3也不會再存重複的相交值。

3 最後建一個int整數的陣列r = new int[ s3.size() ]。

4 最後用foreach遍尋s3，把s3的值存入r裡後回傳r。

Runtime: 2 msMemory Usage: 37.4 MB，勝過98.26%的解法。

程式碼:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
         Set<Integer> s1 = new HashSet<>();
        for(int x: nums1){
            s1.add(x);
        }
        
         Set<Integer> s3 = new HashSet<>();
        for(int s = 0 ; s < nums2.length ; s++){
            if(s1.contains(nums2[s]) ){
                s3.add(nums2[s]);
            }
        }
        
        int[] rr =  new int [s3.size()];
        int index = 0;
        for(int a: s3){
            rr[index] = a;
            index++;
        }

        return rr;
    }
}

討論區裡的解法也類似。但不是用2個hashset，是用一個hashset + queue，有個比較快的作法，是1ms是1 用先將nums1 、 nums2 2個陣列作排序。

2 nums1與nums2逐個比較，nums1[i]比較大就遞增j，nums2[j]比較大就遞增i。

3 不大也不小當然就一樣，就要遞增int k值，這裡要比對是否是"相同的相交值"，若nums1 {1,2,2,1} num2 {2,2,3,3,1}, 雖彼此的2有相交且是相交2次，但回傳陣列還是只有一個2。然後把新的相交值指定給nums1[k]，有指定的k就會遞增。

4 最後回傳不new 一個int 陣列，而是用Arrays.copyOfRange(nums1 , 0 , k) 回傳即可。

程式碼:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0; 
        int k = 0;
        while( i< nums1.length  && j < nums2.length){
            if(nums1[i] < nums2[j]){
                i++;
            }else{
                if(nums1[i] > nums2[j]){
                    j++;
                }else{
                    if(k>0 ){
                         if(nums1[i] != nums1[k-1]){
                            nums1[k] = nums1[i];
                            k++;
                         }
                    }else{
                        nums1[k] = nums1[i];
                        k++;
                    }
                    i++;
                    j++;
                }
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }
}

有個不太好理解的地方:

 別人的寫法:
 if (k == 0 || k > 0 && nums1[i] != nums1[k - 1]) {
                    nums1[k] = nums1[i];
                    k++;
                } 
                
 我的寫法:
 if(k>0 ){
                         if(nums1[i] != nums1[k-1]){
                            nums1[k] = nums1[i];
                            k++;
                         }
                    }else{
                        nums1[k] = nums1[i];
                        k++;
                    }

因為k初值是0，用 nums1[k - 1])來判斷不可以會exception，但

(k == 0 || k > 0 && nums1[i] != nums1[k - 1]) 可以，覺的不好理解才改成我的寫法。