image-20241031092524973

暴力

直接暴力解,肯定是很慢的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int* twoSum(int* nums, int numsSize, int target, int* returnSize) { 
    for(int i=0;i<numsSize;++i)
    {
        for(int j=i+1;j<numsSize;++j)
        {
            if(nums[i]+nums[j]==target)
            {
                int* ret=malloc(sizeof(int)*2);
                ret[0]=i,ret[1]=j;
                *returnSize=2;
                return ret;
            }
        }
    }
    *returnSize=0;
    return NULL;
}

哈希表知识

wp利用哈希表,创建一个hash表,对于每一个x,查询表中是否存在target-x,然后将x插入到哈希表中

这里我们回忆一下hash表,这里展示线性探测法,说实话就是创建一个字典,然后仍键值对进去,通过key来查找

在其中要两个结构体,一个是键值对,还有一个是哈希表

这里的hash函数是通过绝对值key来寻找下标: abs(key)%MAX_SIZE

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
#define MAX_SIZE 10000
typedef struct{
    int key;
    int value;
}HashEntry;

typedef struct{
    HashEntry* entries;
    int size;
}HashMap;

HashMap* createHashMap(){
    HashMap* map=(HashMap*)malloc(MAX_SIZE*sizeof(HashMap));
    map->entries=(HashEntry*)malloc(MAX_SIZE*sizeof(HashEntry));
    for(int i=0;i<MAX_SIZE;i++)
    {
        map->entries[i].key=-1;
    }
    map->size=0;
    return map;
}

int hash(int key){
    return abs(key)%MAX_SIZE;
}

//插入
void put(HashMap* map,int key,int value){
    int index=hash(key);
    while(map->entries[index].key!=-1){
        index=(index+1)%MAX_SIZE;
    }
    map->entries[index].key=key;
    map->entries[index].value=value;
    map->size++; 
}

int get(HashMap* map,int key){
    int index=hash(key);
    while(map->entries[index].key!=-1){
        if(map->entries[index].key==key){
            return map->entries[index].value;
        }
        index=(index+1)%MAX_SIZE;
    }
    return -1;
}

本题使用哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int* twoSum(int* nums,int numsSize,int target,int*returnSize){
    HashMap*map=createHashMap();
    int *result=(int*)malloc(2*sizeof(int));

    for (int i=0;i<numsSize;i++){
        int complement=target-nums[i];
        int complementIndex=get(map,complement);
        if(complementIndex!=-10001){
            result[0]=complementIndex;//如果找到了,因为下面的put我们把他的下标也就是value搞出来
            result[1]=i;
            *returnSize=2;
            free(map->entries);
            free(map);
            return result;
        }
        put(map,nums[i],i);//没找到就把自己作为key下标作为value扔进哈希表
    }
    *returnSize=0;
    free(map->entries);
    free(map);
    return NULL;
}

但是这样好像更崩了,依然没有AC

image-20241031203722891

题解使用 UT_hash_handle hh

了解一下哈希表用uthash实现 | forward

这题可以使用这个来解决

首先还是创建好哈希表

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
struct hashTable{
    int key;
    int val;
    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;
    }
}

然后就是函数实现寻找两数之和部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
            ret[0]=it->val,ret[1]=i;
            *returnSize=2;
            return ret;
        }
        insert(nums[i],i);
    }
    *returnSize=0;
    return NULL;
}

image-20241101084359497