Hashtable hash table and statistics 594, 350, |554, 609, 454, 18

350. Intersection of two arrays II

Given two arrays , Write a function to calculate 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]
explain ：
The number of occurrences of each element in the output result , Should be consistent with the minimum number of occurrences of an element in both arrays .
We can ignore the order of output results .
Answer key ：
1） Two set After de duplication, traverse one of them . because set.toArray There are some problems that have not been realized
2）hashmap, Same in essence 1
3） Double pointer after sorting , Sort the two arrays separately , Two pointers traverse two arrays from scratch , Equal records

sloution：

HashMap<Integer,Integer> map = new HashMap<>();
        //1. Statistics nums1 Number of occurrences of each element in 
        for (int i = 0; i < nums1.length; i++) {
    
            // When Map There's this in the collection key when , Just use this key value , If not, use the default value defaultValue
            int count = map.getOrDefault(nums1[i],0)+1;
            map.put(nums1[i],count);
        }
        //2.  Traverse nums2 Look for the presence of map The elements in are updated at the same time map Of key The number of times 
        int[] result = new int[nums1.length];// Since it's the intersection of two arrays , Then the length must be less than or equal to any array 
        int index = 0;
        for (int target : nums2) {
    
            int count = map.getOrDefault(target,0);
            // Proof element target Exist in map, Just explain nums2 Medium target Is and nums1 Elements with intersection 
            if (count > 0){
    
                result[index++] = target;// Add to result set 
                count --;
                map.put(target,count);// to update map
            }
        }
       // Copy the specified range of the specified array to a new array 
        return Arrays.copyOfRange(result,0,index);

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        //  Sort two arrays .
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len1 = nums1.length, len2 = nums2.length;
        int[] ans = new int[Math.min(len1, len2)];
        int index1 = 0, index2 = 0, index = 0;
        //  As long as an array is traversed, it will jump out of the loop .
        while (index1 < len1 && index2 < len2) {
    
            //  Traversing two arrays , Whoever is young moves his pointer , Equal to record and move the pointer at the same time .
            if (nums1[index1] < nums2[index2]) {
    
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
    
                index2++;
            } else {
    
                ans[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        //  After traversal, return the result array of repeated element length .
        return Arrays.copyOfRange(ans, 0, index);
    }
}

594. The longest harmonious subsequence

A harmonious array means that the difference between the maximum and minimum values of elements in an array is just 1. Now? , Given an array of integers , You need to find the length of the longest harmonious subsequence among all possible subsequences .

Example 1:
Input : [1,3,2,2,5,2,3,7]
Output : 5
reason : The longest harmonious array is ：[3,2,2,2,3].

Answer key ：
1）hash mapping
2） Double pointer after sorting Similar to sliding window
sloution：

class Solution {
    
    public int findLHS(int[] nums) {
    
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int LL = 0;
        for(int i : nums)
        {
    
            if(map.containsKey(i))  
                map.put(i, map.get(i)+1);
            else                    
                map.put(i, 1);
            if(map.containsKey(i - 1))
                LL = Math.max(LL, map.get(i) + map.get(i - 1));
            if(map.containsKey(i + 1))
                LL = Math.max(LL, map.get(i) + map.get(i + 1));
        }
        return LL;
    }
}