[力扣_1] 两数之和
题目入口：点击进入
相关算法：
- 暴力枚举——时间复杂度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位置上有冲突的元素，采用链表将起串接起来（拉链法）
关于这两种方法的详细介绍，同样会在后面的数据结构笔记中详细记录，下方给出逻辑图
那么我们根据题目来看，例如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的位置。
测试代码：
#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