题解 | #两数之和#

LeetCode上做题可以用开源库uthash.h库解决C语言的哈希表问题，比较方便。但牛客网上好像不支持该库的使用，所以就自行把哈希表用到的函数都写了一遍，包括创建哈希表、插入键值对、查找键值对、删除键值对以及删除整个哈希表。解题的思路大致跟官方答案一致，可以参考一下哈希表各个函数的用法，加深印象

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
 #define TableSize 10000
 #define NoExist -1 //表示要寻找的值不存在

 typedef struct HashNode{
    int key; //整数数值
    int val;    //下角标
    struct HashNode* Next;
 } HashNode; //定义哈希结点

 typedef struct HashTable{
    HashNode** Buckets;
 } HashTable; //定义哈希桶（哈希结点数组）

 HashTable* CreatHashTable(); //创建哈希表
 int Hash(int key); //哈希函数（索引函数，可自定义）
 void Insert(HashTable* hashtable,int key, int val); //插入函数
 int Search(HashTable* hashtable,int TargetKey); //搜索函数
 void RemoveHashNode(HashTable *hashtable, int Targetkey);//删除键值对
 void DestoryHashTable(HashTable *hashtable);//摧毁已有的哈希表


int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    HashTable *hashtable=CreatHashTable();
    for(int Count=0;Count<numbersLen;Count++){
        int IfExist=Search(hashtable,target-numbers[Count]);
        if(IfExist!=NoExist){
            *returnSize=2;
            int* Result=(int *)malloc(sizeof(int)*2);
            Result[0]=IfExist+1;
            Result[1]=Count+1;
            return Result;
        }
        else
            Insert(hashtable, numbers[Count], Count);
    }
    *returnSize=0;
    return NULL;
}

HashTable* CreatHashTable(){ 
    HashTable *hashtable=(HashTable *)malloc(sizeof(HashTable));
    hashtable->Buckets=(HashNode**)malloc(sizeof(HashNode*)*TableSize);
    for(int Idx=0;Idx<TableSize;Idx++)
        hashtable->Buckets[Idx]=NULL;

    return hashtable;
}

int Hash(int key){
    return key%TableSize>0?key%TableSize: -(key%TableSize);
}

void Insert(HashTable* hashtable,int key, int val){
    int Idx=Hash(key);
    HashNode* NewNode=(HashNode *)malloc(sizeof(HashNode));
    if(hashtable->Buckets[Idx]==NULL){
        NewNode->Next=NULL;
        hashtable->Buckets[Idx]=NewNode;
    }
    else{
        NewNode->Next=hashtable->Buckets[Idx];
        hashtable->Buckets[Idx]=NewNode;
    }
    NewNode->key=key;
    NewNode->val=val;
}

int Search(HashTable* hashtable,int TargetKey){
    /*当key在哈希表中存在时返回其在数字中的坐标
    否则返回-1表示不存在该值*/
    int Idx=Hash(TargetKey);
    HashNode *Temp=hashtable->Buckets[Idx];
    while(Temp!=NULL){
        if(Temp->key==TargetKey)
            return Temp->val;
        Temp=Temp->Next;
    }
    return -1;
}

void RemoveHashNode(HashTable *hashtable, int TargetKey){
    int Idx=Hash(TargetKey);
    HashNode *CurrNode=hashtable->Buckets[Idx];
    HashNode *PreNode=NULL;
    while(CurrNode->key!=TargetKey && CurrNode!=NULL){
        PreNode=CurrNode;
        CurrNode=CurrNode->Next;
    }
    //如果CurrNode==NULL说明无Target结点，无操作
    if(CurrNode!=NULL){
        PreNode->Next=CurrNode->Next;
        free(CurrNode);
    }
}

void DestoryHashTable(HashTable *hashtable){
    for(int Idx=0;Idx<TableSize;Idx++){
        if(hashtable->Buckets[Idx]!=NULL){
            HashNode *Temp=hashtable->Buckets[Idx];
            HashNode *Del=NULL;
            while(Temp!=NULL){
                Del=Temp;
                Temp=Temp->Next;
                free(Del);
            }
        }
    }
    free(hashtable->Buckets);
    free(hashtable);
}