原题链接:
https://leetcode.cn/problems/intersection-of-two-arrays-ii/

哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(var x : nums1){
            int count = hash.getOrDefault(x,0);
            count++;
            hash.put(x,count);
        }

        int [] ans = new int[Math.min(nums1.length,nums2.length)];
        int k = 0;
        for(var x : nums2){
            int count = hash.getOrDefault(x,0);
            if(count > 0){
                count--;
                ans[k++] = x;

                hash.put(x,count);
            }
        }

        return Arrays.copyOfRange(ans,0,k);
    }
}

解法2: 排序 + 双指针 (感觉有些问题 如果无序的话 应该不能这么做)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    /*
    *   排序 + 双指针
    * */
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int [] ans = new int[Math.min(nums1.length,nums2.length)];
        int k = 0;
        for(int i = 0 , j = 0 ; i < nums1.length && j < nums2.length;){
            if(nums1[i] < nums2[j]){
                i++;
            }else if(nums1[i] > nums2[j]){
                j++;
            }else{
                ans[k] = nums1[i];
                k++;
                i++;
                j++;
            }
        }
        
        // k 后面的多余元素不要直接去除掉
        return Arrays.copyOfRange(ans,0, k);
    }
}