[Java][Example] Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Answer1 : Works but is a bad answer O(n^2)
Use a hashmap to store the indexs of nums1 and nums2 matched.
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hm = new HashMap<Integer, Integer>();
        ArrayList<Integer> arrList = new ArrayList<Integer>();
       
        for(int i=0; i<nums1.length; i++){
            for(int j=0; j<nums2.length; j++){
                if(nums1[i]==nums2[j]){
                    if(!hm.containsKey(i) && !hm.containsValue(j)){
                        hm.put(i, j);
                        arrList.add(nums1[i]);
                    }
                }
            }
        }
       
        int[] result = new int[arrList.size()];
        for(int i=0; i<arrList.size(); i++){
            result[i] = arrList.get(i);
        }
        return result;
    }
}

Better Solution O(n):
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i: nums1){
            if(map.containsKey(i)){
                map.put(i, map.get(i)+1);
            }else{
                map.put(i, 1);
            }
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i: nums2){
            if(map.containsKey(i)){
                if(map.get(i)>1){
                    map.put(i, map.get(i)-1);
                }else{
                    map.remove(i);
                }
                list.add(i);
            }
        }
        int[] result = new int[list.size()];
        int i =0;
        while(i<list.size()){
            result[i]=list.get(i);
            i++;
        }
        return result;
    }
}