用hash解决leetcode01两数之和

题意分析：在一个数组中找到和为target的两个元素，并返回下标数组

1. 做法一：双层暴力循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int *twoSum(int *nums,int numsSize,int target,int *returnSize)
{
    static int ret[10]={0};
   for(int i=0;i<numsSize;i++){
       for(int j=i+1;j<numsSize;j++){
           if(nums[i]+nums[j]==target){
             //int* ret=(int *)malloc(sizeof(int)*10);
              ret[0]=i,ret[1]=j;
              *returnSize=2;
               return ret;
           }
       }
   }
   *returnSize=0;
   return NULL;
}

2. 做法二：hash

  ​       **利用hash的做法即为涉及到查找，我们设置一个集合，初始状态为空，在遍历原数组的过程中，就在这个集合中查找target-a[i],如果有则停止查找，如果没有则将该元素加入集合**

  ```c
  //leetcode支持ut_hash函数库
  typedef struct {
      int key;
      int value;
      UT_hash_handle hh;//make this structure hashable
  }map;
  map* hashMAP=NULL;
  void hashMapAdd(int key,int value)
  {
      map*s;
      HASH_FIND_INT(hashMap,&key,s);
      if(s==NULL){
          s=(map*)malloc(sizeof(map));
          s->key=key;
          HASH_ADD_INT(hashMap,key,s);
      }
      s->value=value;
  }
  map* hashMapFind(int key)
  {
      map*s;
     HASH_FIND_INT(hashMap,&key,s);
      return s;
  }
  void hashMapCleanup()
  {
      map*cur,*tmp;
      HASH_ITER(hh,hashMap,cur,tmp){
          HASH_DEL(hashMap,cur);
          free(cur);
      }
  }
  void hashPrint(){
      map*s;
      for(s=hashMap;s!=NULL;s=(map*)(s->hh.next))
      {
          print("key %d ,value %d\n",s->key,s->value);
      }
  }
  int *twoSum(int *nums,int numsSize,int target,int *returnSize)
  {
      int i,*ans;
      map* hashMapRes;
      hashMap=NULL;
      ans=(int*)malloc(sizeof(int)*2);
      for(i=0;i<numsSize;i++){
          hashMapAdd(nums[i],i);
      }
      hashPrint();//经典打印检查
      for(i=0;i<numsSize;i++){
          hashMapRes=hashMapFind(target-nums[i]);
          if(hashMapRes&&hashMapRes->value!=i){
              ans[0]=i;
              ans[1]=hashMapRes->value;
              *returnSize=2;
              return ans;
          }
      }
      hashMapCleanup();
      *returnSize=0;
      return NULL;
  }
  ```

  ​     此种做法中涉及到很多使用头文件函数库uthash.h中的用法，当然我们也可以将这些封装好的函数进行手搓，关于函数库uthash.h会在下一篇中介绍

  **手搓hash**

  ```c
  //每个元素的关键是值和下标
  struct node{
      int key;
      int value;
      struct node*link;
  };
  struct node *hash[10000]={NULL};
  //这里的整数值都比较小，可以考虑直接取余法(质数)，但是会处理一些冲突
  int HASH(int key)
  {
     return key%13;
  }
  int *twoSum(int *nums,int numsSize,int target,int *returnSize)
  {
      int*a=(int*)malloc(sizeof(int)*2);
      for(int i=0;i<numsSize;i++){
          //以下代码为target>nums[i]
          if(hash[HASH(target-nums[i])]==NULL){
              struct node *p=(struct node*)malloc(sizeof(struct node));  
              p->key=nums[i];p->value=i;p->link=NULL;
              hash[HASH(nums[i])]=p;                                                                                                                          
          }else{
              struct node *q=hash[HASH(target-nums[i])];
              while(q!=NULL){
                  if(q->value!=i)//不同下标
                  {
                      a[0]=q->value,a[1]=i;
                      *returnSize=2;
                      return a;
                  }
                  q=q->link;
              }
          }
      }
      *returnSize=0;
      return NULL;
  }
  ```

  ​      **但是测试用例中会出现target<nums[i]的情况，即可能出现hash数组下标为负数的情况，以上版本不能通过**