哈希表之Uthash应用

Uthash总览

哈希表介绍

哈希表就是通过一个映射函数f(key)将一组数据散列存储在数组中的一种数据结构。在这哈希表中，每一个元素的key和它的存储位置都存在一个f(key)的映射关系，我们可以通过f(key)快速的查找到这个元素在表中的位置

Uthash简介

Uthash是一个用C语言编写的开源哈希表库，它提供了简单易用的接口来创建和操作哈希表。Uthash支持多种数据类型作为键，并且可以动态调整哈希表的大小以适应数据量的变化

hot100中Uthash的应用

1. 两数之和

LeetCode 1. 两数之和

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

Uthash应用： 使用Uthash存储数组元素及其索引，在遍历数组时，计算目标值与当前元素的差值，并在哈希表中查找该差值是否存在

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//哈希表结构体
typedef struct{
    int key;
    int val;
    UT_hash_handle hh;
} hashTable;

//定义全局变量哈希表指针，指向表头
hashTable* table;

//查找功能
hashTable* find(int key){
    hashTable* tmp;
    HASH_FIND_INT(table,&key,tmp);
    return tmp;
}

//插入功能
void insert(int key,int val){
    hashTable* node=find(key);
    if(node==NULL){
        hashTable* tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=key;
        tmp->val=val;
        HASH_ADD_INT(table,key,tmp);
    }
    else{
        node->val=val;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    table=NULL;
    for(int i=0;i<numsSize;i++){
        hashTable* tmp=find(target-nums[i]);
        if(tmp){
            int* ret=(int*)malloc(sizeof(int)*2);
            ret[0]=tmp->val;
            ret[1]=i;
            return ret;
        }
        else{
            insert(nums[i],i);
        }
    }
    *returnSize=0;
    return NULL;
}

本题的解题思路是：

  1. 遍历数组，对于每个元素，计算目标值与当前元素的差值，并在哈希表中查找该差值是否存在
  2. 如果存在，返回对应的索引；如果不存在，将当前元素及其索引插入哈希表中
  3. 最后是在O(n)的时间复杂度内解决问题

2. 字母异位词分组

LeetCode 49. 字母异位词分组

问题描述： 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串

Uthash应用： 使用Uthash存储排序后的字符串作为键，原始字符串列表作为值，将异位词分组

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//结构体定义
typedef struct{
    char* key;          //键：排序后的字符串
    char** list;        //值：原始字符串列表
    int cnt;            //当前字符串对应的列表大小
    int capacity;       //列表容量
    UT_hash_handle hh;  //哈希表句柄
} hashTable;

hashTable* table;

//qsort比较函数需要使用的cmp函数
int cmp(const void* a,const void* b){
    return (*(char*)a-*(char*)b);
}

hashTable* find(char* key){
    hashTable* tmp;
    HASH_FIND_STR(table,key,tmp);
    return tmp;
}

//这里需要注意字符串的+1是为了存储字符串的结束符'\0'
hashTable* insert(char* key,char* str){
    hashTable* node=find(key);
    if(node==NULL){
        hashTable* tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=malloc(strlen(key)+1);
        strcpy(tmp->key,key);
        tmp->capacity=10;
        tmp->cnt=0;
        tmp->list=malloc(sizeof(char*)*tmp->capacity);
        tmp->list[tmp->cnt]=malloc(strlen(str)+1);
        strcpy(tmp->list[tmp->cnt],str);
        tmp->cnt++;
        HASH_ADD_STR(table,key,tmp);
    }
    else{
        //如果容量不够则扩容
        if(node->cnt>=node->capacity){
            node->capacity*=2;
            node->list=realloc(node->list,sizeof(char*)*node->capacity);
        }

        node->list[node->cnt]=malloc(strlen(str)+1);
        strcpy(node->list[node->cnt],str);
        node->cnt++;
    }
}

char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    table=NULL;

    //构建哈希表，插入键与值
    for(int i=0;i<strsSize;i++){
        int len=strlen(strs[i]);
        char* sortedStr=malloc(len+1);
        strcpy(sortedStr,strs[i]);
        qsort(sortedStr,len,sizeof(char),cmp);
        insert(sortedStr,strs[i]);
        free(sortedStr);
    }

    *returnSize=HASH_COUNT(table);
    char*** res = malloc(sizeof(char**) * (*returnSize));
    *returnColumnSizes = malloc(sizeof(int) * (*returnSize));
    int idx=0;
    hashTable* node,*tmp;

    //遍历哈希表，构建结果集
    HASH_ITER(hh,table,node,tmp){
        res[idx]=malloc(sizeof(char*)*node->cnt);
        (*returnColumnSizes)[idx]=node->cnt;
        for(int j=0;j<node->cnt;j++){
            res[idx][j]=malloc(strlen(node->list[j])+1);
            strcpy(res[idx][j],node->list[j]);
        }
        idx++;
    }

    //清理哈希表，释放内存
    HASH_ITER(hh,table,node,tmp){
        free(node->key);
        for(int j=0;j<node->cnt;j++){
            free(node->list[j]);   
        }
        free(node->list);
        HASH_DEL(table,node);
        free(node);
    }
    return res;
}

本题的解题思路是：

  1. 遍历字符串数组，对于每个字符串，排序后作为键插入哈希表
  2. 如果键已存在，则将原始字符串添加到对应的值列表中
  3. 最后遍历哈希表，构建结果集

3. 最长连续序列

LeetCode 128. 最长连续序列

问题描述： 给定一个未排序的整数数组，找出最长连续序列的长度

Uthash应用： 使用Uthash存储数组元素，遍历数组时，检查每个元素的前后连续元素是否存在，计算最长连续序列长度

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define MAX(a,b) ((a)>(b)?(a):(b))
//哈希表结构体
typedef struct{
    int key;
    UT_hash_handle hh;
} hashTable;

int longestConsecutive(int* nums, int numsSize){
    if(numsSize==0) return 0;
    hashTable* table=NULL;

    //构建哈希表,去重
    for(int i=0;i<numsSize;i++){
        hashTable* tmp;
        HASH_FIND_INT(table,&nums[i],tmp);
        if(tmp==NULL){
            tmp=(hashTable*)malloc(sizeof(hashTable));
            tmp->key=nums[i];
            HASH_ADD_INT(table,key,tmp);
        }
    }

    int longest=0;
    hashTable* node,* findNode,* tmp;
    HASH_ITER(hh,table,node,tmp){
        int cur=node->key;
        int prev=cur-1;
        HASH_FIND_INT(table,&prev,findNode);
        //不是序列的起点，跳过
        if(findNode!=NULL) continue; 
        int cnt=1;
        int next=cur+1;
        HASH_FIND_INT(table,&next,findNode);
        while(findNode!=NULL){
            next++;
            cnt++;
            HASH_FIND_INT(table,&next,findNode);
        }
        longest=MAX(cnt,longest);
    }

    //释放哈希表内存
    HASH_ITER(hh,table,node,tmp){
        HASH_DEL(table,node);
        free(node);
    }
    return longest;
}

本题的解题思路是：

  1. 使用Uthash构建哈希表，这一步可以去重
  2. 遍历哈希表，找到每个可能连续序列的起点，这一步算是一个优化，不需要对每个数字都找到最后，只需要对序列起点开始寻找cnt，计算连续长度
  3. 最后比较longest与cnt，返回最长序列长度即可

4. 路径总和Ⅲ

LeetCode 437. 路径总和 III

问题描述： 给定一个二叉树和一个整数目标和targetSum，找出路径总和等于目标和的路径数量。路径不需要从根节点开始或结束，但必须向下移动（只能从父节点到子节点）

Uthash应用： 使用Uthash存储前缀和及其出现次数，在遍历二叉树时，计算当前路径的前缀和，并查找是否存在满足条件的前缀和

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//哈希表结构体
typedef struct{
    long long sum;
    int cnt;
    UT_hash_handle hh;
} PrefixSumNode;

static PrefixSumNode* prefixMap=NULL;

void dfsPathSum(struct TreeNode* root,long long currSum,int targetSum,int* ans){
    if(root==NULL) return;
    //计算当前前缀和
    currSum+=root->val;
    //计算还需要的前缀和
    long long need=currSum-targetSum;
    PrefixSumNode* find;
    //如果能找到need，则说明存在满足条件的路径
    HASH_FIND(hh,prefixMap,&need,sizeof(long long),find);
    if(find){
       *ans+=find->cnt;
    }
    //将当前前缀和加入哈希表
    PrefixSumNode* currNode=NULL;
    HASH_FIND(hh,prefixMap,&currSum,sizeof(long long),currNode);
    if(currNode==NULL){
       currNode=(PrefixSumNode*)malloc(sizeof(PrefixSumNode));
       currNode->sum=currSum;
       currNode->cnt=1;
       HASH_ADD(hh,prefixMap,sum,sizeof(long long),currNode);
    } else{
       currNode->cnt++;
    }
    //递归计算左右子树
    dfsPathSum(root->left,currSum,targetSum,ans);
    dfsPathSum(root->right,currSum,targetSum,ans);
    //回溯，移除当前前缀和
    currNode->cnt--;
    if(currNode->cnt==0){
        HASH_DEL(prefixMap,currNode);
        free(currNode);
    }
}

int pathSum(struct TreeNode* root, int targetSum){
    int ans=0;
    prefixMap=NULL;
    // 加入初始前缀和0，1次
    PrefixSumNode* baseNode=(PrefixSumNode*)malloc(sizeof(PrefixSumNode));
    baseNode->sum=0;
    baseNode->cnt=1;
    HASH_ADD(hh,prefixMap,sum,sizeof(long long),baseNode);

    dfsPathSum(root,0,targetSum,&ans);
    //释放哈希表内存
    PrefixSumNode* node,*tmp;
    HASH_ITER(hh,prefixMap,node,tmp){
        HASH_DEL(prefixMap,node);
        free(node);
    }
    return ans;
}

本题使用哈希表的优势如下：

  1. 使用Uthash存储前缀和及其出现次数，可以在O(1)时间内查找是否存在满足条件的前缀和
  2. 通过前缀和的概念，可以高效地计算路径和，类似与两数之和的去查找need
  3. 本题的一个重点就是need=currSum-targetSum，通过这个公式可以快速定位到满足条件的前缀和，从而计算路径数量

解题思路如下：

  1. 使用DFS遍历二叉树，使用哈希表储存当前节点的前缀和（当前路径上的），通过前缀和之差计算出其中子路径的路径之和，判断是否等于targetSum
  2. 哈希表还要储存cnt，表示当前前缀和出现的次数，因为可能存在多条路径的前缀和相同
  3. 注意本题还需要回溯，在DFS返回上一层时，需要将当前前缀和的计数减一，确保哈希表中只包含当前路径上的前缀和信息

5. 从前序与中序遍历序列构造二叉树

LeetCode 105. 从前序与中序遍历序列构造二叉树

问题描述： 给定两个整数数组preorder和inorder，其中preorder是二叉树的前序遍历，inorder是二叉树的中序遍历，请构造二叉树并返回其根节点

Uthash应用： 使用Uthash存储中序遍历数组中每个元素的索引，便于在构建二叉树时快速定位根节点在中序遍历中的位置，本题使用哈希表主要在于优化查找位置

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//结构体定义
typedef struct{
    int key;
    int val;
    UT_hash_handle hh;
} hashTable;

hashTable* table;

 struct TreeNode* buildTreeHelper(int* preorder,int lpre,int rpre,int* inorder,int lin,int rin){
    if(lpre>rpre || lin>rin) return NULL;
    // 找到根节点（先序序列当前区间的第一个节点）在中序遍历中的位置
    int rootVal=preorder[lpre];
    hashTable* find;
    HASH_FIND_INT(table,&rootVal,find);
    int k=find->val;
    // 构造二叉树
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=rootVal;
    int leftSize=k-lin;

    root->left=builedTreeHelper(preorder,lpre+1,lpre+leftSize,inorder,lin,k-1);
    root->right=builedTreeHelper(preorder,lpre+leftSize+1,rpre,inorder,k+1,rin);
    
    return root;
 }

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    table=NULL;
    // 构建哈希表，存储中序遍历数组中每个元素的索引
    for(int i=0;i<inorderSize;i++){
        hashTbale* tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=inorder[i];
        tmp->val=i;
        HASH_ADD_INT(table,key,tmp);
    }
    struct TreeNode* root=buildTreeHelper(preorder,0,preorderSize-1,inorder,0,inorderSize-1);

    hashTable* tmp,* curr;
    HASH_ITER(hh,table,curr,tmp){
        HASH_DEL(table,curr);
        free(curr);
    }
    return root;
}

本题相比如下的原始版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct  TreeNode* Tree(int* preorder,int lpre,int rpre,int *inorder,int lin,int rin){
    if(lpre > rpre || lin > rin)
        return NULL;
    int k;
    for(k=lin;k<=rin;k++){
        if(inorder[k]==preorder[lpre]){
            break;
        }
    }
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=preorder[lpre];
    int leftSize = k - lin;
    root->left=Tree(preorder,lpre+1,lpre+leftSize,inorder,lin,k-1);
    root->right=Tree(preorder,lpre+leftSize+1,rpre,inorder,k+1,rin);
    return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return Tree(preorder,0,preorderSize-1,inorder,0,inorderSize-1);
}

使用哈希表的优势如下：

  1. 使用Uthash存储中序遍历数组中每个元素的索引，可以在O(1)时间内查找根节点在中序遍历中的位置
  2. 避免了在每次递归中使用循环查找根节点位置，提升了整体构建二叉树的效率

解题思路如下：

  1. 使用Uthash构建哈希表，存储中序遍历数组中每个元素的索引
  2. 递归构建二叉树，利用哈希表快速定位根节点在中序遍历中的位置，划分左右子树
  3. 最后释放哈希表内存，返回构建好的二叉树根节点

6. 多数元素

LeetCode 169. 多数元素

问题描述： 给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素

Uthash应用： 使用Uthash存储数组元素及其出现次数，遍历数组时，更新哈希表中的计数，最后找到出现次数超过n/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
28
29
30
31
32
33
34
35
//哈希表结构体
typedef struct{
    int key;
    int val;
    UT_hash_handle hh;
} hashTable;

int majorityElement(int* nums, int numsSize){
    hashTable* table=NULL;
    // 构建哈希表，统计每个元素的出现次数
    for(int i;i<numsSize;i++){
        hashTable* node;
        HASH_FIND_INT(table.&nums[i],node);
        if(node==NULL){
            node=(hashTable*)malloc(sizeof(hashTable));
            node->key=nums[i];
            node->val=1;
            HASH_ADD_INT(table,key,node);
        } else{
            node->val++;
        }
    }

    int ans;
    int maxCnt=0;
    hashTable* node,* tmp;
    // 遍历哈希表，找到出现次数最多的元素
    HASH_ITER(hh,table,node,tmp){
        if(node->val>maxCnt){
            max=node->val;
            ans=node->key;
        }
    }
    return ans;
}

本题除了技巧方法，其他方法较为好想,在这里使用哈希表主要还是为了熟悉哈希表的使用

7. 随机链表的复制

LeetCode 138. 随机链表的复制

问题描述： 给定一个链表，每个节点包含一个额外的随机指针，该指针可以指向链表中的任何节点或null。请实现一个函数来复制这个链表

Uthash应用： 使用Uthash存储原始节点与其对应的复制节点的映射关系，在遍历原始链表时，创建复制节点并更新随机指针

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 哈希表结构体
typedef struct{
    struct Node* key;
    struct Node* val;
    UT_hash_handle hh;
} hashTable;

struct Node* copyRandomList(struct Node* head){
    if(!head) return NULL;
    hashTable* table=NULL;
    struct Node* curr=head;
    // 构建哈希表，存储原始节点与复制节点的映射关系
    while(curr){
        struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
        newNode->val=curr->val;
        newNode->next=NULL;
        newNode->random=NULL;
        
        hashTable* tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=curr;
        tmp->val=newNode;
        HASH_ADD_PTR(table,key,tmp);

        curr=curr->next;
    }

    // 更新复制节点的next和random指针
    curr=head;
    while(curr){
        hashTable* find;
        HASH_FIND_PTR(table,&curr,find);
        struct Node* newNode=find->val;

        // 设置next指针
        if(curr->next){
            HASH_FIND_PTR(table,&curr->next,find);
            newNode->next=find->val;
        } else{
            newNode->next=NULL;
        }

        // 设置random指针
        if(curr->random){
            HASH_FIND_PTR(table,&curr->random,find);
            newNode->random=find->val;
        } else{
            newNode->random=NULL;
        }

        curr=curr->next;
    }

    // 返回复制链表的头节点
    hashTable* findHead;
    HASH_FIND_PTR(table,&head,findHead);
    struct Node* newHead=findHead->val;

    hashTable* curr,* tmp;
    HASH_ITER(hh,table,curr,tmp){
        HASH_DEL(table,curr);
        free(curr);
    }

    return newHead;
}

本题的解题思路是：

  1. 遍历原始链表，使用哈希表存储每个原始节点与其对应的复制节点的映射关系
  2. 再次遍历原始链表，使用哈希表更新复制节点的next和random指针
  3. 最后返回复制链表的头节点

除了上述的方法外，还有一种哈希表+递归的方法:

  1. 我们用哈希表记录每一个节点对应新节点的创建情况。
  2. 遍历该链表的过程中，我们检查当前节点的后继节点和当前节点的随机指针指向的节点的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。
  3. 当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。
  4. 注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

下面我会给出代码实现：

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
28
29
30
31
32
33
34
35
36
// 哈希表结构体
typedef struct{
    struct Node* key;
    struct Node* val;
    UT_hash_handle hh;
} hashTable;

hashTable* table;

struct Node* deepCopy(struct Node* head){
    if(head==NULL) return NULL;
    hashTable* tmp;
    HASH_FIND_PTR(table,&head,tmp);
    if(tmp==NULL){
        struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
        newNode->val=head->val;
        tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=head;
        tmp->val=newNode;
        HASH_ADD_PTR(table,key,tmp);
        newNode->next=deepCopy(head->next);
        newNode->random=deepCopy(head->random);
    }
    return tmp->val;
}

struct Node* copyRandomList(struct Node* head){
    table=NULL;
    struct Node* newHead=deepCopy(head);
    hashTable* curr,* tmp;
    HASH_ITER(hh,table,curr,tmp){
        HASH_DEL(table,curr);
        free(curr);
    }
    return newHead;
}

8. 相交链表

LeetCode 160. 相交链表

问题描述： 给定两个单链表的头节点headA和headB，找出并返回两个链表相交的起始节点。如果两个链表没有交点，返回null

Uthash应用： 使用Uthash存储第一个链表的节点地址，在遍历第二个链表时，检查节点是否存在于哈希表中，找到相交节点

代码实现

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
28
29
typedef struct{
    struct ListNode* key;
    UT_hash_handle hh;
} hashTable;

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
    hashTable* table=NULL;
    struct ListNode* curr=headA;
    // 构建哈希表，存储第一个链表的节点地址
    while(curr){
        hashTable* tmp=(hashTable*)malloc(sizeof(hashTable));
        tmp->key=curr;
        HASH_ADD_PTR(table,key,tmp);
        curr=curr->next;
    }

    // 遍历第二个链表，检查节点是否存在于哈希表中
    curr=headB;
    while(curr){
        hashTable* find;
        HASH_FIND_PTR(table,&curr,find);
        if(find){
            return curr;
        }
        curr=curr->next;
    }

    return NULL;
}

本题的解题思路是：

  1. 遍历第一个链表，将每个节点的地址存储在哈希表中
  2. 遍历第二个链表，检查每个节点是否存在于哈希表中
  3. 如果找到相交节点，返回该节点；如果遍历结束未找到，返回null

9. 和为k的子数组

LeetCode 560. 和为k的子数组

问题描述： 给定一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的连续子数组的个数

Uthash应用： 使用Uthash存储前缀和及其出现次数，在遍历数组时，计算当前前缀和，并查找是否存在满足条件的前缀和

前缀和思想 本题与之前的路径总和Ⅲ(- 4. 路径总和Ⅲ)类似，都是利用前缀和的思想来解决问题。前缀和是指从数组开头到当前位置的元素之和。通过计算当前前缀和与目标值的差值，我们可以快速定位到满足条件的前缀和，从而计算出连续子数组的个数

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef struct {
    int sum;          // 当前前缀和
    int count;        // 前缀和出现的次数
    UT_hash_handle hh; // uthash 处理的哈希句柄
} HashMapEntry;

int subarraySum(int* nums, int numsSize, int K) {
    HashMapEntry* sum_map = NULL;  // 哈希表的头指针
    HashMapEntry* entry;
    int current_sum = 0;
    int count = 0;

    // 初始情况下，前缀和为0出现一次
    entry = (HashMapEntry*)malloc(sizeof(HashMapEntry));
    entry->sum = 0;
    entry->count = 1; // sum=0 出现 1 次
    HASH_ADD_INT(sum_map, sum, entry);

    for (int i = 0; i < numsSize; i++) {
        current_sum += nums[i];  // 更新当前的前缀和
        int target = current_sum - K;

        // 查找前缀和为 target 的条目
        HASH_FIND_INT(sum_map, &target, entry);
        if (entry) {
            count += entry->count;  // 如果存在，累加计数
        }

        // 更新当前前缀和在哈希表中的计数
        HASH_FIND_INT(sum_map, &current_sum, entry);
        if (entry) {
            entry->count += 1;
        } else {
            entry = (HashMapEntry*)malloc(sizeof(HashMapEntry));
            entry->sum = current_sum;
            entry->count = 1;
            HASH_ADD_INT(sum_map, sum, entry);
        }
    }

    // 清理哈希表内存
    HashMapEntry *tmp, *current_entry;
    HASH_ITER(hh, sum_map, current_entry, tmp) {
        HASH_DEL(sum_map, current_entry);
        free(current_entry);
    }

    return count;
}

本题的解题思路是：

  1. 使用Uthash构建哈希表，存储前缀和及其出现次数
  2. 遍历数组，计算当前前缀和，并查找是否存在满足条件的前缀和
  3. 如果存在，累加计数；如果不存在，更新当前前缀和在哈希表中的计数
  4. 最后返回计数结果

总结

以上题目均是我在刷题过程中碰见的有关哈希表的题目，目前还在c语言，没有自带的哈希表数据结构，只能使用Uthash来进行实现，这些题目既可以帮助我学习哈希表的使用方法，也可以帮助我入门Uthash的使用，等到后面使用c++和python的时候应该就会轻松很多

leetcode刷题笔记 > C语言
#算法 #哈希表
哈希表之Uthash应用
https://moon1784734830.github.io/2026/01/12/哈希表之Uthash应用/
作者
兰卡黄
发布于
2026年1月12日
许可协议