217. 存在重复元素
https://leetcode-cn.com/problems/contains-duplicate/
给定一个数组，如果任意一值在数组中出现至少两次，函数返回 True 。如果数组中每个元素都不相同，则返回 False 。
example:
输入: [1,2,3,1]
输出: true
解题思路
哈希表：创建一个空字典dict.get()函数返回键值对中的值，如果存在则证明重复，输出True;不存在则可以赋值一个任意‘值’（这里设为了1）如若循环结束，则返回FALSE。时间复杂度：O(n) , 空间负责度：O(n)
代码
class Solution(object):
def containsDuplicate(self
, nums
):
hashset
= {}
for x
in nums
:
if hashset
.get
(x
):
return True
hashset
[x
]=1
return False
巧方法
利用题干信息，只要重复就返回True，比长度即可。
return(len(set(nums
))!=len(nums
))
136. 只出现一次的数字
链接：https://leetcode-cn.com/problems/single-number/solution/python3he-ha-xi-biao-duo-chong-fang-fa-by-johnsonw/
给定一个数组，仅有一个数字只出现一次，其余都出现两次，找到这个数。
example:
输入: [2,2,1]
输出: 1
解题思路
哈希表：hashset.get(x,0)令字典的初始值为0，只要出现一次键，值就+1。用于统计键的次数。找到值为1的键即可。时间复杂度：O(2n)=O(n),空间复杂度:O(n)
代码
class Solution(object):
def singleNumber(self
, nums
):
hashset
= {}
for x
in nums
:
hashset
[x
] = hashset
.get
(x
,0) + 1
for key
,value
in hashset
.items
():
if value
== 1:
return key
349. 两个数组的交集
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/
给定两个数组，返回它们的交集。
解题思路
哈希表，先构建一个字典存nums1，再判断nums2是否在字典中，存在则保存于一个新的字典中。（不用列表的原因是字典与集合具有不重复性，列表没有）时间复杂度:O(m+n),空间复杂度:O(m)
代码
class Solution:
def intersection(self
, nums1
: List
[int], nums2
: List
[int]) -> List
[int]:
hashset1
= {}
for i
in nums1
:
if not hashset1
.get
(i
):
hashset1
[i
]=1
set = {}
for j
in nums2
:
if hashset1
.get
(j
):
set[j
] = 1
return set
解题思路
set算法的时间复杂度:O(m+n)，空间复杂度：O(m+n)
代码
class Solution(object):
def intersection(self
, nums1
, nums2
):
set1
= set(nums1
)
set2
= set(nums2
)
if len(nums1
)>=len(nums2
):
return(x
for x
in set1
if x
in set2
)
else:
return(x
for x
in set2
if x
in set1
)
1. 两数之和
链接：https://leetcode-cn.com/problems/two-sum/
给定一个数组nums和一个目标值target，问在nums中是否能找到两个数和为target，返回他们下标。不可重复使用，只有一个答案。
example：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
哈希表：在数组中找到目标数并返回下标，用哈希表很方便。构建一个哈希表：
用enumerate(nums)函数返回下标：[0,“2”],[1,“7”],[2,“11”],[3,“15”]用hashmap[num] = ind 构建映射用hashmap.get(target-num) is not None,判断target-num是否存在于字典中，存在即输出[ind,hashmap.get(target-num)] 时间复杂度：O(n),遍历一遍nums即可。空间复杂度：O(n)
代码
class Solution(object):
def twoSum(self
, nums
, target
):
hashmap
= {}
for ind
,num
in enumerate(nums
):
if hashmap
.get
(target
- num
) is not None:
return [ind
,hashmap
.get
(target
-num
)]
hashmap
[num
] = ind
594. 最长和谐子序列
链接：https://leetcode-cn.com/problems/longest-harmonious-subsequence/
给定一个序列，找到最长和谐序列。（和谐序列的最大值与最小值仅相差1），可不连续选取。
example:
输入: [1,3,2,2,5,2,3,7]
最长的和谐数组是：[3,2,2,2,3].
输出: 5
解题思路
哈希表：只输出长度，所以用哈希表存储数字出现的次数。再遍历哈希表，如果num+1也在哈希表中，则计算次数和的大小。时间复杂度：O(2n),遍历数组+哈希表空间复杂度：O(n)，哈希表，res只占常数空间
代码
class Solution(object):
def findLHS(self
, nums
):
hashmap
= {}
for i
in nums
:
hashmap
[i
] = hashmap
.get
(i
,0) + 1
res
=0
for num
in hashmap
:
if num
+1 in hashmap
:
res
= max(res
,hashmap
[num
]+hashmap
[num
+1])
return res
128. 最长连续序列
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
example:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解题思路
哈希表：代码与思路见大神，求最长连续子序列长度，设哈希表记录当前数字的最长长度。长度=hashset[num-1]+hashset[num+1]+1: num左右两个数所记录的最长长度再加一个自己。用res缓存下来，去迭代得到最大res。此时的时间复杂度为O(n),但可以优化下，hashset[num-left],hashset[num+right]应当与我的hashset[num]长度相同(都在一个子序列中），直接赋值避免重复运算。时间复杂度：O(n)空间复杂度：O(n),哈希表
代码
class Solution(object):
def longestConsecutive(self
, nums
):
hashset
= {}
res
= 0
for num
in nums
:
if num
not in hashset
:
left
= hashset
[num
-1] if num
-1 in hashset
else 0
right
= hashset
[num
+1] if num
+1 in hashset
else 0
hashset
[num
] = left
+right
+1
hashset
[num
-left
] = hashset
[num
+right
] = left
+right
+1
res
= max(res
,hashset
[num
])
return res
集合法（更好理解）
class Solution(object):
def longestConsecutive(self
, nums
):
nums
= set(nums
)
res
=0
for num
in nums
:
if num
-1 not in nums
:
tmp
= 1
while num
+1 in nums
:
tmp
+= 1
num
+= 1
res
= max(tmp
,res
)
return res
时间复杂度：O(n)空间复杂度：O(n)
