两数之和.md

两数之和

原题链接：

https://leetcode.cn/problems/two-sum/description/

题目：

给定一个整数数组nums和一个整数目标值target,请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

解法一：暴力枚举

枚举数组中的每个数x,遍历数组看看是否存在target-x,每次便利的时候不需要匹配x之前存在的数，因为都和x匹配过

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
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* res=malloc(sizeof(int)*2);
                res[0]=i,res[1]=j;
                *returnSize=2;
                return res;
            }
        }
    }
    *returnSize=0;
    return NULL;
}

复杂分析：

• 时间复杂度: $O(N^2)$,最坏的情况下数组中任意两个数都要被匹配一次，
• 空间复杂度： $O(1)$

解法二：哈希表

创建一个哈希表，使用哈希表将寻找target-x的复杂度降到O(1)，对于每一个x，我们首先查询哈希表中是否存在target-x,然后将x插入到里面。

// 定义哈希表结构体
struct HashTable{
    int key;
    int value;
    UT_hash_handle hh;// 用于处理哈希表的结构体
};
struct HashTable* HashTable;//定义全局的哈希表
//查找函数，用于在哈希表中查找键值为ikey的项
struct HashTable* find(int ikey){
    struct HashTable* temp;
    HASH_FIND_INT(HashTable,&ikey,temp);//使用宏在哈希表中查找
    return temp;
}

//插入函数
void insert(int ik,int iv){
    struct HashTable* order=find(ik);
    if(order==NULL){
    struct HashTable* temp=malloc(sizeof(struct HashTable));//创建新哈希表项
    temp->key=ik,temp->value=iv;
    HASH_ADD_INT(HashTable,key,temp);
}else{
    order->value=iv;
    }
}
int* twoSum(int* nums,int numsSize,int target,int* returnSize){
    HashTable=NULL;
    for(int i=0;i<numsSize;i++){
        struct HashTable* order=find(target-nums[i]);
        if(order!=NULL){
                    int* res=malloc(sizeof(int)*2);
                    res[0]=order->value,res[1]=i;
                    *returnSize =2;
                    return res;
                }
                insert(nums[i],i);
        }
        *returnSize=0;
        return NULL;
}

复杂度分析

• 时间复杂度： $O(N)$,对于每一个元素 x，我们可以 $o(1)$ 地寻找 target - x。
• 空间复杂度： $O(N)$,z主要为建立哈希表