1.两数之和
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
暴力枚举
思路
枚举数组中的每一个数x，寻找数组中是否存在target-x。
# 时间复杂度：O(N^2)
# 空间复杂度：O(1)
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 []哈希表
思路
利用Hash map记录值与索引的关系，并查找target-val的索引是否存在，如果存在且不等于目前val的索引，则返回。
# 时间复杂度：O(N)
# 空间复杂度：O(N)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, val in enumerate(nums):
hashmap[val] = index
for index, val in enumerate(nums):
temp = hashmap.get(target-val)
if temp is not None and temp != index:
return [index, temp]
return []49.字母异位词分组
题目
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
利用 dict.get() 函数
思路
当且仅当它们的排序字符串相等时，两个字符串时字母异位词。
算法
维护一个dict，首先枚举字符串，对每个字符串内部排序并转换成元组（字典的键为不可变类型），利用dict.get(key, [])，存在则返回值，不存在则返回[]。
# 时间复杂度：O(N*K*log(K))
# 空间复杂度：O(N*K)
class Solution:
def groupAnagrams(self, strs):
ans = {}
for s in strs:
key = tuple(sorted(s))
ans[key] = ans.get(key, [])+ [s]
return list(ans.values())计数分类
思路
当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。
算法
将每个字符串s转换为字符数count，由26个非负整数组成，表示 \text{a}a，\text{b}b，\text{c}c 的数量等。我们使用这些计数作为哈希映射的基础。
# 时间复杂度：O(N*K)
# 空间复杂度：O(N*K)
class Solution:
def groupAnagrams(self, strs):
ans = {}
for s in strs:
count = [0]*26
for c in s:
count[ord(c) - ord('a')] += 1
key = tuple(count)
ans[key] = ans.get(key, [])+[s]
return list(ans.values())242. 有效的字母异位词
题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
暴力枚举
思路
对s与t分别排序，排序后的字符串如果相等，则为字母异位词。
# 时间复杂度：O(N*log(N))
# 空间复杂度：O(1)
class Solution(object):
def isAnagram(self, s, t):
if sorted(s) == sorted(t):
return True
else:
return False哈希表
思路
对s与t分别构建哈希表，key为每个字符，index为出现的次数。
# 时间复杂度：O(N)
# 空间复杂度：O(N)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
dict1, dict2 = {}, {}
for item in s:
dict1[item] = dict1.get(item, 0)+1
for item in t:
dict2[item] = dict2.get(item, 0)+1
return dict1 == dict2
