Leetcode学习01

题目描述：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1] 

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

解题思路

关键词：哈希表 查找

将给定的值扫描一遍，扫描的时候同时查找是否和前面已经扫过的值匹配（也就是：和为所需要的值 target）

而这个“匹配”的过程，其实就是一种“查找” ，在查找是否具有满足条件的值。也就是在查找x之前 是否存在 target-x的值

思路一 暴力全扫描

扫一个值时，查查看前头是否有target-x在前头。

（也就是使得nums[i]+nums[j]=target的存在）

思路二 采用哈希表存储

用哈希表这一数据结构进行数据的存储，实现快速查找

哈希表：也叫散列表，是一种数据结构，哈希表中存储的是键值对，也就是key-value这个对。

在哈希表中可以通过key ->哈希函数->索引 快速查找到相应的值

作用：这种数据结构方便我们进行数据的查找，在哈希表中查找key十分快速

在python中，可以通过内置数据结构 dic() 获得一个哈希表 ，也就是说，一个字典就可以看成是一个哈希表，在哈希表中我们想要查找一个key是否在里面，只需要将key输入，就可以快速查出是否有键值key对应的对 是否存在 是何值

这道题通过构建一个哈希表，边扫描边存入哈希表，然后在查找的时候直接查找表中是否有键值为target-x的元素存在（对于哈希表来说实现这中寻找键值的查找过程十分轻松）于是实现了快速的查找！！

时间复杂度:o(N),N为数组元素个数 顺带一提，查找target-x这个过程只需o(1)

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def twoSum(self, nums, target):

       """

       :type nums: List[int]

       :type target: int

       :rtype: List[int]

       """

       Hass=dict() #字典，作为哈希表

       for i,nu in enumerate(nums):

           if target-nu in Hass: #如果这个键值存在于哈希表中

               return [Hass[target-nu],i]  #将键值对应的索引输出 而且因为这个边扫描边
#存入Hass表中的过程，本质上来说就是对先前元素的查找！

           Hass[nums[i]]=i #题目要的是 索引 因此键值对存入时也存的是索引

       return [] #当查不到的时候return一个空的呗

启示

  1. 哈希表（散列表）这个数据结构可以迅速的实现查找，在哈希表中查找键值是否存在与键值对应的值是多少是很轻松的

  2. 你在哈希表中存了什么数据，你就是在什么范围中查找，就像是一个数据库一样，你放了啥，你就只能在你放了的东西范围中查找~

  3. 边扫描边存入，可以实现“记录先前已遍历过的元素”这一作用。当还需要“回头”做一些操作的时候就可以方便的调出记录进行查找与维护啥的。

  4. 像这种匹配问题，转化一下就是一个查找问题！

    找两个数满足什么什么条件，变化一下，就是对于一个变量来说，对其不同值查找是否存在一个数，可以“迎合”这个变量此时取值，满足条件，因此本质上这种问题就是一个查找问题！！！要学会问题的转化