刷题笔记——哈希表（C）

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路

哈希+开放定址法

注意题干条件：

只需声明一个基础常量base=10^4，遍历数组更新哈希表，然后反向遍历哈希表，找出第k个大的数即可。

代码实现

#define BASE 10000
int hash[2*BASE+5];

int findKthLargest(int* nums, int numsSize, int k){
    memset(hash, 0, sizeof( hash)) ;
    int i;
    for(i = 0; i < numsSize; ++i) {
        int v = nums[i] + BASE;
        ++hash[v];
    }
    for( i = 2*BASE; i >= 0; --i) {
        while(hash[i]) {
            --k;
            --hash[ i];
        if(k == 0) {
            return i - BASE;
            }
        }
    }
    return -1;
}

1002. 查找共用字符 - 力扣（LeetCode）

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

解决思路

==> 返回每个数组元素中都出现且出现次数最少的那个字符

1° 定义一个哈希表minhash存储每个字符的出现次数的最小值，再定义一个辅助哈希表hash记录每个元素中的字符出现次数，与minhash比较更新最小值，hash需每轮重置。

2° 注意字符数组的返回：由于确定返回数组的元素是单个字符，所以每个数组元素只需申请2个char空间的内存（'\0'作为结尾字符）

代码实现

char ** commonChars(char ** words, int wordsSize, int* returnSize){
    int hash[26];
    int minhash[26];
    memset(hash, 0, sizeof(hash));
    memset(minhash,10,sizeof(minhash));
    for(int i = 0; i < wordsSize; i++){
        memset(hash,0,sizeof(hash));
        for(int j = 0; j < strlen(words[i]); j++){
            hash[words[i][j]-'a']++;
        }
        for(int x = 0; x < 26; x++){
            minhash[x] = fmin(minhash[x],hash[x]);
        }       
    }
    int sum = 0;
    for(int i = 0; i < 26; i++){
        sum += minhash[i];
    }
    char **ans = (char **)malloc(sizeof(char*)*sum);
    *returnSize = 0;
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < minhash[i]; j++){
            ans[*returnSize] = malloc(sizeof(char)*2);
            ans[(*returnSize)][0] = i + 'a';
            ans[(*returnSize)++][1] = '\0'; 
        }
    }
    return ans;
}

1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

解题思路

1° 引用uthash，构建哈希表结构体

2° 依次遍历数组，用目标和target与当前元素作差，记为it，若哈希表中已存在，则返回。若不存在，则将it加入表中。直到遍历完为止，否则返回空。

代码实现

struct hashTable{
    int val;
    int key;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable*find(int ikey){
    struct hashTable*tmp;
    HASH_FIND_INT(hashtable,&ikey,tmp);
    return tmp;
}

void insert(int ikey, int ival){
    struct hashTable* it = find(ikey);
    if(it == NULL){
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable,key,tmp);
    }else{
        it->val = ival;
    }
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for(int i = 0; i < numsSize; i++){
        struct hashTable* it = find(target-nums[i]);
        if(it != NULL){
            int *ret = malloc(sizeof(int)*2);
            *returnSize = 2;
            ret[0] = it->val;
            ret[1] = i; 
            return ret;
        }
        insert(nums[i],i); 
    }
    *returnSize = 0;
    return NULL; 
}

560. 和为 K 的子数组 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

解题思路

前缀和+哈希表

1° 首先我们要知道子数组，是指连续的一段，如[1，2，3]：[1,2]，[2,3]是子数组，[1,3]不是。

2° 每遍历到一个元素，计算当前位置的preSum，查看当前哈希表中，有没有满足key是 preSum-k 的键值对。为什么？

假设从位置 i 到位置 j 恰好为满足题意的一个子数组，那么从位置 i 到位置 j 的元素和等于k，即preSum[j] - preSum[i] == k，这么一移项，得到preSum[j] - k = preSum[i]，这就意味着对于当前位置来说，只要哈希表中存在满足key是 preSum-k 的键值对，那么就找到了一个子数组。接下来看具体操作。

3° 引用uthash，构建哈希表结构体，首先将（0，1）添加进哈希表中

4° 声明变量count记录子数组的个数，ret记录当前前缀和，依次遍历数组，若哈希表中存在need == ret - k；则加上对应的val。

5 ° 每遍历一个元素，都要更新哈希表。若当前前缀和已在哈希表中出现则val++，否则该前缀和加入哈希表，val==1

为什么？当前前缀已经出现在了哈希表中，说明了当前的这个元素是0，所以前缀和不变，那么0也得算进子数组里吧？这也是为什么count+=val而不是直接count++。比如：对于数组[0, 0]，k = 0 ，有3个子数组，[][][0]，[0]，[0, 0]，如果我们不更新val值，那么得到的答案为1，显然是错误的。

6° 最后返回count值（这里略过了释放哈希表的操作）

代码实现

int subarraySum(int* nums, int numsSize, int k) {
    // 创建哈希表，key：前缀和，value：key 对应的前缀和的个数
    typedef struct {
        int key;
        int val;
        UT_hash_handle hh;
    } hashTable;

    hashTable* hashtable = NULL;

    hashTable* zeroSum = (hashTable*)malloc(sizeof(hashTable));
    zeroSum->key = 0;
    zeroSum->val = 1;
    HASH_ADD_INT(hashtable, key, zeroSum);

    int preSum = 0;
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        preSum += nums[i];
        int need = preSum - k;
        hashTable* tmp;
        HASH_FIND_INT(hashtable, &need, tmp);
        if (tmp != NULL) {
            count += tmp->val;
        }
        hashTable* curSum;
        HASH_FIND_INT(hashtable, &preSum, curSum);
        if (curSum == NULL) {
            curSum = (hashTable*)malloc(sizeof(hashTable));
            curSum->key = preSum;
            curSum->val = 1;
            HASH_ADD_INT(hashtable, key, curSum);
        } else {
            curSum->val++;
        }
    }
    return count;
}