[力扣_1] 两数之和

20
[ LeetCode ] [ 算法基础 ]

题目入口：点击进入

相关算法：

  • 暴力枚举——时间复杂度O(n²)，空间复杂度O(1)
  • 哈希映射——时间复杂度O(n),空间复杂度O(n)

思路和算法：

这应该是梦的开始哈哈哈哈哈哈哈，使用暴力枚举最坏的情况用两层循环一个一个去匹配的话，得走N²次，哈希的话只需要走一次。

哈希映射

使用哈希表，可以将寻找 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

可以知道，之前在github上边C语言曾开源过Hash的结构，有兴趣的可以看看：

点击观看

当然，对应uthash库相关的结构在上方博文中都有介绍，但是为了更加了解hash表的底层结构，我决定自己构造

我们根据java之前的hash结构可以了解，hash就是通过键找到值，给定一个关键字，就能快速的查找到此关键词存储的位置

我们需要一个hash函数通过关键字生成hash值，再来找到对应的地址，在数据结构日后的笔记中，会详细记录这种结构，在我构造的时候，我采用的是：

  • 关键字为整型，对给定元素去模查到对应的hash位置（求余）
  • 对在hash位置上有冲突的元素，采用链表将起串接起来（拉链法）

关于这两种方法的详细介绍，同样会在后面的数据结构笔记中详细记录，下方给出逻辑图

img

那么我们根据题目来看，例如A={7,2,11,5}，target=9这个数组，因为是求和操作，在任意一个数组元素与其余数组元素相加的情况下，必须有9-A[i]=A[j]，我们只需要

  • 求于为数组长度，这样任何元素的值定位都不会超过这个数组的长度
  • 例如9-A[0]%A.size=9-7=4，那么于7匹配的位置的值就要是二，那么我们就在7%4的位置查询是否有2的值与之对应，如若没有，则将7插入2%4这个位置
  • 指针走向元素值为2的情况下，重复之前的操作，先求出与其对应的值为9-2=7，我们现在2%4这个位置查找是否有7这个元素，如果有，则返回7在数组中的定位，如果没有，则将其插入7%4的位置。

img

img

测试代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int val;//哈希值结构
    int key;
}HashData;

typedef struct HashNode {
    HashData Data;//哈希结点结构
    struct HashNode* next;
}HashNode;

typedef struct HashMap//哈希表结构
{
    int size;
    HashNode* itabl;
}HashMap;
int FindHash(HashMap* Hash, HashData Data, int e)//从哈希表中查询目标值
{
    HashNode* p;//控制元素链表
    HashNode* s;
    if (Hash->itabl[abs(Data.val) % Hash->size].Data.val == INT_MIN)//当查询位置为空时，目标值一定不存在
    {
        if (Hash->itabl[abs(e) % Hash->size].Data.val == INT_MIN)//插入目标值对应的定位，由于采用拉链法
        {                                                        //需要插入结点到最后一个位置
            Hash->itabl[abs(e) % Hash->size].Data.val = Data.val;
            Hash->itabl[abs(e) % Hash->size].Data.key = Data.key;
            return -1;//返回-1，未找到目标值对应定位
        }
        p = Hash->itabl + (abs(e) % Hash->size);//插入结点
        while (p->next != NULL)
        {
            p = p->next;
        }
        p->next = (HashNode*)malloc(sizeof(HashNode));
        p = p->next;
        p->next = NULL;
        p->Data.val = Data.val;
        p->Data.key = Data.key;
        return -1;
    }
    else//目标值对应定位上有元素
    {
        p = Hash->itabl + abs(Data.val) % Hash->size;
        while (p != NULL && p->Data.val != e)//判断是否与目标值相等的元素
        {
            p = p->next;
        }
        if (p != NULL && p->Data.val == e)//如果有，则直接返回目标值
        {
            return (p->Data.key + 1);//+1是为了更好操作，无实际作用
        }
        else {
            if (Hash->itabl[abs(e) % Hash->size].Data.val == INT_MIN)//如果没有找到，则在其上插入目标元素
            {
                Hash->itabl[abs(e) % Hash->size].Data.val = Data.val;
                Hash->itabl[abs(e) % Hash->size].Data.key = Data.key;
                return -1;
            }
            p = Hash->itabl + (abs(e) % Hash->size);
            while (p->next != NULL)
            {
                p = p->next;
            }
            p->next = (HashNode*)malloc(sizeof(HashNode));
            p = p->next;
            p->next = NULL;
            p->Data.val = Data.val;
            p->Data.key = Data.key;
            return -1;
        }
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashMap Hash;
    Hash.itabl = (HashNode*)malloc(sizeof(HashNode) * numsSize);
    Hash.size = numsSize;

    for (int i = 0; i < numsSize; i++)
    {
        Hash.itabl[i].Data.val = INT_MIN;
        printf("%d   ", Hash.itabl[i].Data.val);
        Hash.itabl[i].next = NULL;
    }
    printf("\n");
    int temp;
    HashData data;
    int k;
    int RetunArr[2];
    for (int i = 0; i < numsSize; i++)
    {
        temp = target - nums[i];

        data.val = nums[i];
        data.key = i;
       
        //打印哈希表
        /*for (int i = 0; i < numsSize; i++)
        {
            HashNode* p = Hash.itabl + i;
            while (p != NULL)
            {
                printf("%d,%d  ", p->Data.val, p->Data.key);
                p = p->next;
            }
            printf("\n");
        }
        */
        k = FindHash(&Hash, data, temp);
        if (k != -1)
        {
            *returnSize = 2;
            RetunArr[0] = k - 1;
            RetunArr[1] = i;
            return RetunArr;
        }
    }
    *returnSize = 2;
    RetunArr[0] = -1;
    RetunArr[1] = -1;
    return RetunArr;
}
int main()
{
    int nums[3] = { 3,2,4 };
    int a;
    int *b;
    b=twoSum(nums, 3, 6, &a);
    printf("[%d,%d]", b[0], b[1]);



    system("pause");
    return 0;

}

答题代码：

typedef struct 
{
    int val;
    int key;
}HashData;

typedef struct HashNode{
    HashData Data;
    struct HashNode *next;
}HashNode;

typedef struct HashMap
{
    int size;
    HashNode *itabl;
}HashMap;
int FindHash(HashMap*Hash,HashData Data,int e)
{
    HashNode*p;
    HashNode*s;
    if(Hash->itabl[abs(Data.val)%Hash->size].Data.val==-260000)
    {
        if(Hash->itabl[abs(e)%Hash->size].Data.val==-260000)
        {
            Hash->itabl[abs(e)%Hash->size].Data.val=Data.val;
            Hash->itabl[abs(e)%Hash->size].Data.key=Data.key;
            return -1;
        }
        p=Hash->itabl+(abs(e)%Hash->size);
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=(HashNode*)malloc(sizeof(HashNode));
        p=p->next;
        p->next=NULL;
        p->Data.val=Data.val;
        p->Data.key=Data.key;
        return -1;
    }
    else
    {
        p=Hash->itabl+abs(Data.val)%Hash->size;
        while(p!=NULL&&p->Data.val!=e)
        {
            p=p->next;
        }
        if(p!=NULL&&p->Data.val==e)
        {
            return p->Data.key+1;
        }
        else{
        if(Hash->itabl[abs(e)%Hash->size].Data.val==-260000)
        {
            Hash->itabl[abs(e)%Hash->size].Data.val=Data.val;
            Hash->itabl[abs(e)%Hash->size].Data.key=Data.key;
            return -1;
        }
        p=Hash->itabl+(abs(e)%Hash->size);
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=(HashNode*)malloc(sizeof(HashNode));
        p=p->next;
        p->next=NULL;
        p->Data.val=Data.val;
        p->Data.key=Data.key;
        return -1;
        }
    }
}



int* twoSum(int* nums, int numsSize, int target, int* returnSize){
   HashMap Hash;
   Hash.itabl=(HashNode*)malloc(sizeof(HashNode)*numsSize);
   Hash.size=numsSize;
   
   for(int i=0;i<numsSize;i++)
   {
       Hash.itabl[i].Data.val=-260000;
       Hash.itabl[i].next=NULL;
   }

   int temp;
   HashData data;
   int k;
   int *RetunArr=(int*)malloc(sizeof(int)*2);
   for(int i=0;i<numsSize;i++)
   {
      temp=target-nums[i];
      data.val=nums[i];
      data.key=i;
      k=FindHash(&Hash,data,temp);
      if(k!=-1)
      {
            *returnSize=2;
            RetunArr[0]=k-1;
            RetunArr[1]=i;
            return RetunArr;
      }
   }
*returnSize=2;
RetunArr[0]=-1;
RetunArr[1]=-1;
return RetunArr;
}

暴力枚举

暴力枚举就简单多了，直接两层for循环，拿数组中的每一个元素与其他元素去相加，看是否匹配上给定的target ：

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;
}

A

本文链接：

https://nullcode.fun/46.html
1 + 9 =
快来做第一个评论的人吧~