大一那会偶然听说过leetcode，那时刚学算法感觉这玩意太高大上了…（其实是感觉好难）。 注册后就尘封了。
学到现在，终于感受到了算法的重要性…看来以后算法练习也要提上日程了QWQ !

第一题，两数和

题目：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

中文:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

第一种方法:

遍历两遍数组，暴力破解。通过for循环的嵌套，每一个元素进行尝试，正确则返回。
代码如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i] + nums[j] == target:
                        return [i,j]
        
        return None

分析：
当数组长度为n时，时间复杂度为O(n²)。
关于时间和空间，两者相比之下我更愿意用空间来换取时间。当然，使用的空间也不能太过分。

第二种解法：

第一种方法的时间复杂度是 O(n²)，这是因为遍历了两次数组，那如果我们只遍历一次数组，那么时间自然就降下来了->O(n)
我们知道x + y = target，我们遍历的时候已经获取到了X，则y = target - x。所以此时我们只需寻找满足Y值的数就可以了。
而判断Y值是否在数组中，我们可以用if语句来实现。但这有个问题，题目要求不能重复使用自己。如果target = X + X时则错误。
代码如下：

1
2
3
4
5
6
7
8
9
10
for index, num in enumerate(nums):
    # 找到Y值
    find_num = target - num
    # 记录当前下标
    my_index = index
    # 判断数组中是否存在Y值
    if find_num in nums :
        fine_index = nums.index(find_num)
        if fine_index != my_index: # 判断Y值的下标与X值是否一样
            return [my_index, fine_index]

分析：
与其他语言相比，python的if语句无疑是走了捷径。

第三种解法：

既然第二种解法的时间复杂度是O(n)，那如果是O(1)的话速度无疑会更快。
通过看大佬的解答得知一种数据结构hashmap，一种键值一一对应的数据结构。这让我联想到了python的 dict。
通过对字典的索引，无疑可以减少遍历带来的时间问题，因此我们把数组的下标 index 和数组的内容 value联系起来。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
# 把数组转换成字典
dict_nums = {}
for index, num in enumerate(nums):
    dict_nums[num] = index

for index, num in enumerate(nums):
    find_num = target - num
    my_index = index
    if find_num in dict_nums.keys():
        if dict_nums[find_num] != my_index:
            find_index = dict_nums[find_num]
            return [my_index, find_index]

哈希表

这一题所涉及的知识点–哈希表
哈希表是一种数据结构，它使用哈希函数组织数据，以支持快速插入和快速搜索。

哈希表简介

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 xx 到首字母 F(x)F(x) 的一个函数关系），在首字母为 WW 的表中查找 “王” 姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母” 是这个例子中哈希函数的函数法则 F()F()，存放首字母的表对应哈希表。关键字和函数法则理论上可以任意确定。

哈希表是使用 O(1)O(1) 时间进行数据的插入删除和查找，但是哈希表不保证表中数据的有序性，这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。

哈希表的原理

哈希表的关键思想是：

  • 存储
    1. 开创一块连续存储空间，通常是数组。(这块连续的空间称为散列表或哈希表)
    2. 把key通过固定的算法函数(哈希函数) 转换成一个整型数字
    3. 把该数字对数组长度进行取余，取余的结果则是数组(哈希表)下标。
    4. 将value的值存储在以该数字为下标的数组空间中

当读取时，过程与存储类似。

  • 读取
    1. 将key通过同样的过程进行转换
    2. 用转换后的值(即下标)，去访问对应数组下标。

这样就能够快速的通过数组下标定位元素了!!!!! TQLLLLLL!

哈希表冲突

理想情况下，如果我们的哈希函数是完美的一对一映射，我们将不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。因为余数的个数是有限的(0-9)。比如，哈希函数y = x % 5 中，1987和2 的余数都是2，这是一个冲突。

因此，哈希函数的设计就十分重要。冲突解决算法应该解决以下几个问题：

  • 如何组织在同一个桶中的值？
  • 如果为同一个桶分配了太多的值，该怎么办？
  • 如何在特定的桶中搜索目标值？

好的哈希函数的特点：

  1. 尽量使关键字对应的记录均匀分配在哈希表里面
  2. 关键字极小的变化可以引起哈希值极大的变化。

哈希冲突解决的办法有许多，我提一下用的比较多的链地址法。
上面说到，数组的空间是会用完的。链地址法的原理是：如果遇到冲突，他会在源地址新建一个空间，然后以链表结点的形式插入到该空间。

比如说我有一堆数据{1,12,26,337,353…}，而我的哈希算法是H(key)=key mod 16，第一个数据1的哈希值f(1)=1，插入到1结点的后面，第二个数据12的哈希值f(12)=12，插入到12结点，第三个数据26的哈希值f(26)=10，插入到10结点后面，第4个数据337，计算得到哈希值是1，遇到冲突，但是依然只需要找到该1结点的最后链结点插入即可，同理353。

总结

不知道说什么，但算法真的好好好好好好好van！~~！