（哈希表、数组操作）697、数组的度

/*
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:

输入: [1, 2, 2, 3, 1]
输出: 2
解释: 
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

示例 2:

输入: [1,2,2,3,1,4,2]
输出: 6

注意:

    nums.length 在1到50,000区间范围内。
    nums[i] 是一个在0到49,999范围内的整数。
*/

int findShortestSubArray(int* nums, int numsSize)
{
    int* hash_times = (int*)calloc(50000 , sizeof(int));
    int* hash_start = (int*)malloc(50000 * sizeof(int));
    memset(hash_start, -1, 50000);
    int* hash_end = (int*)calloc(50000 , sizeof(int));
    int max_time = 0;
    int min_len = 50000;
    
    for(int i = 0; i < numsSize; i++)
    {
        hash_times[nums[i]]++;//计算元素的频次
        if(hash_times[nums[i]] > max_time)//记录最大频次
            max_time = hash_times[nums[i]];
        if(hash_start[nums[i]] == -1)//记录元素最先出现的位置
            hash_start[nums[i]] = i;
        hash_end[nums[i]] = i;//记录元素最后出现的位置
    }
    
    for(int i = 0; i < numsSize; i++)
    {
        if(hash_times[nums[i]] == max_time)
        {
            if(min_len > hash_end[nums[i]] - hash_start[nums[i]] + 1)
                min_len = hash_end[nums[i]] - hash_start[nums[i]] + 1;
        }
    }
    
    return min_len;
}

/*
解题思路：
1、记录所给数组中每个元素出现的频次，并记录最大频次；
2、记录每个元素第一次出现时的位置和最后一次出现时的位置；
3、遍历频次表，找到最大频次对应的元素，并找到该元素在位置表中对应的子序列的长度：
子序列的长度 = 该元素最后一次出现时的位置 - 该元素第一次出现时的位置 + 1；
4、从得到的子序列的长度中，找到最小长度即为需要返回的值。

实现方法：
1、如何记录数组中每个元素出现的频次？
使用一个初始值为0的哈希表hash_times累加记录即可。
2、如何记录每个元素第一次出现的位置？
初始化一个值为-1的哈希表hash_start，在遍历数组nums时，以nums[i]作为key值，如果对应的value值为-1，
则说明该元素是第一次出现，记录其此时的下标即可。
3、如何记录每个元素最后一次出现的位置？
使用一个哈希表hash_end，以nums[i]为key值，以其对应的下标i为value值，当nums数组遍历完一遍后，其对应
的value值即为该元素最后出现的位置。
4、如何找到频次最高的元素所组成的最短子序列的长度？
遍历频次哈希表，如果元素nums[i]对应的频次是最大频次，则找到其对应的起始位置哈希表和终点
位置哈希表中的位置记录，计算两位置之间的差值，并记录找到所有差值中最小的那个即可。
*/