編號349：兩個數組的交集

題意：給定兩個數組，編寫一個函數來計算它們的交集。

「說明：」
輸出結果中的每個元素一定是唯一的。
我們可以不考慮輸出結果的順序。

思路

注意題目特意說明：「輸出結果中的每個元素一定是唯一的，也就是說輸出的結果的去重的， 同時可以不考慮輸出結果的順序」

這道題用暴力的解法時間複襍度是O(n^2)，那來看看使用哈希法進一步優化。

可以發現，貌似用數組做哈希表可以解決這道題目，把nums1的元素，映射到哈希數組的下表上，然後在遍歷nums2的時候，判斷是否出現過就可以了。

但是要注意，「使用數據來做哈希的題目，都限制了數值的大小，例如哈希表：可以拿數組儅哈希表來用，但哈希值不要太大題目中衹有小寫字母，或者數值大小在[0- 10000] 之內等等。」

而這道題目沒有限制數值的大小，就無法使用數組來做哈希表了。

「而且如果哈希值比較少、特別分散、跨度非常大，使用數組就造成空間的極大浪費。」

代碼

public class 三四九題兩個數組的交集 {
    public static void main(String[] args) {
        int [] num1 = {1,2,2,1};
        int [] num2 = {2,2};
        int[] arraryIntersect = arraryIntersectSort(num1, num2);
        System.out.println(Arrays.toString(arraryIntersect));

    }
    //使用哈希法
    public static int [] arraryIntersect(int [] num1, int [] num2){
        HashMap<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int num : num1){
            if( !map.containsKey(num) ){
                map.put( num,1 );
            }else{
                map.put( num,map.get(num) 1 );
            }
        }

        for( int num : num2){
            if( map.containsKey( num )){
                map.put( num, map.get(num)-1);
                if( map.get(num) == 0 ){
                    map.remove( num );
                    list.add( num );
                }
            }
        }

        int res [] =new int [list.size()];

        for( int i = 0; i < list.size(); i   ){
            res[i] = list.get(i);
        }

        return res;
    }

    //使用排序的方法利用雙指針
    public static int [] arraryIntersectSort(int [] num1, int [] num2){
        List<Integer> list = new ArrayList<>();
        Arrays.sort( num1 );
        Arrays.sort( num2 );
        int p1 = 0;
        int p2 = 0;
        while( p1 < num1.length && p2 < num2.length ){
            if( num1[p1] == num2[p2]) {
            list.add( num1[p1] );
            p1  ;
            p2  ;
            }else if( num1[p1] < num2[p2] ){
                p1  ;
            }else{
                p2  ;
            }
        }
        int res [] =new int [list.size()];

        for( int i = 0; i < list.size(); i   ){
            res[i] = list.get(i);
        }
        return res;
    }
}