[数据结构与算法]LeetCode 1.两数之和——扩展知识点：哈希

关键词：哈希

来学走路，写代码不熟练就是0。加黑的是出了疑问的地方。

想的很复杂，但是手笨，那不行，先来个最简单的无脑N²
python的if for不打括号
for i in range(int1) 或 range(int1,int2)
python3函数格式示例 def haha(self, aa:int, bb:List[int]) -> List[int]:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        findflag=0
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):# j从i+1开始找，range可以这么用
                #题中确保了已有这两个数且必须是不同的两个数
                if nums[i]+nums[j]==target and i!=j: 
                    findflag=1
                    break
            if findflag==1:
                break
        return [i,j]

看一下怎么优化

字典是另一种可变容器模型，且可存储任意类型对象。
字典的每个键值 key:value 对用冒号 : 分割，每个键值对之间用逗号 , 分割，整个字典包括在花括号 {} 中 ,格式如下所示：
d = {key1 : value1, key2 : value2 }

官方给出哈希表。如果用c写要自己写算法。

for i, item in enumerate(xx)
Python 字典 in 操作符用于判断键是否存在于字典中，如果键在字典 dict 里返回 true，否则返回 false。 not in 相反
在Python中，字典是通过散列表或说哈希表实现的。

python3：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable=dict()
        # 命名最好不要用相近的 num建议改item等
        for i,num in enumerate(nums):
            if target-num in hashtable:
                return [hashtable[target-num],i]
            hashtable[nums[i]]=i #题目已确保是两个数，答案需要下标，下标做value 写在后面可以少一次写入

再用c写一次，看了标答我才知道有个库uthash.h可以直接用，干脆把哈希一起看了。
c语言下uthash库的使用1:基础用法、2:详解，以及删除等更多函数，还不太会用，可以做这篇里的练习题，有必要的话 😛

typedef struct my_hash{
    int key;
    int val;
    UT_hash_handle hh;
}my_hash;

my_hash *table=NULL;

my_hash* hashFind(int ikey)
{
    my_hash *s=NULL;
    HASH_FIND_INT(table,&ikey,s);
    return s;
}

void hashInsert(int ikey, int ival)
{
    my_hash* s=hashFind(ikey); 
    if(s==NULL){ //本题可以不管数字重复情况，重复情况见下面哈希补充知识点
        s=malloc(sizeof(*s));
        s->key=ikey;
        s->val=ival;
        HASH_ADD_INT(table,key,s); //注意这里！第二个参数写结构体内的变量名，详见定义
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    table=NULL; //初始化指针好习惯！
    for(int i=0;i<numsSize;i++){
        my_hash *s=hashFind(target-nums[i]);
        if(s!=NULL){ //key-num val-下标
            *returnSize=2;
            int* ret=malloc(sizeof(int)*2);
            ret[0]=s->val;
            ret[1]=i;
            return ret;
        }
        hashInsert(nums[i],i);
    }
    *returnSize=0;
    return NULL;
}

此外，一对多的哈希怎么办？
（还没看完，看完再找两道哈希的算法和面试题）——初步：开放定址法、链地址法；进阶：多阶哈希表、一致性哈希1、2、3

c++/java/golang的之后再补，为了熟悉各语言基本用法