242. 有效的字母异位词 https://leetcode-cn.com/problems/valid-anagram/
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。即字母一样但顺序不同。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解：
对s和t进行排序，比较排序好的字符串。O(NlogN)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
用hashmap来对字符串中的每个字母计数。O(N)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
def count_aph(s):
aph_s = dict()
for char in s:
aph_s[char] = aph_s.get(char, 0) + 1 # 找不到key就返回0
return aph_s
aph_s = count_aph(s)
aph_t = count_aph(t)
if aph_s == aph_t:
return True
return False
1. 两数之和 https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
解：
暴力求解，遍历所有可能的第一个数，嵌套遍历第二个数。O(N2)，很可能超时
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if nums is None or len(nums) <= 1 :
return []
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 []
哈希表，y = target - x，枚举x，查询 y。可以先遍历一遍同时存哈希表，再枚举x查询y。
也可以一边遍历存哈希表的时候立刻就查询。O(N)。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if nums is None or len(nums) <= 1 :
return []
n = len(nums)
visited = dict()
for i in range(n):
visited[nums[i]] = i
for i in range(n):
y = target - nums[i]
if y in visited and visited.get(y) != i: # y在哈希表中且不重复利用同样的元素
return [i, visited.get(y)]
return []
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if nums is None or len(nums) <= 1 :
return []
n = len(nums)
visited = dict()
for i in range(n):
y = target - nums[i]
if y in visited and visited.get(y) != i:
return [visited.get(y), i] # 这时候就是索引i在后了
visited[nums[i]] = i
return []
15. 三数之和 https://leetcode-cn.com/problems/3sum/
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ? 找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解：
暴力求解，三层嵌套，O(N3)，不写了。
x+y+z = target，枚举x、y，再去哈希表中查询target - x - y。O(N2)
关于下面代码存进哈希表的方法，进一步解释：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
nums.sort() # 先排序一下，便于判重
res = set()
for i, x in enumerate(nums[: -2]):
if i >= 1 and x == nums[i-1]:
continue
# 对每个确定的x, 找y和z,退化成两数之和的问题
d = {}
for y in nums[i+1:]:
if not y in d:
d[-x-y] = 1 # 如果y不在d中，就把匹配当前y的z（即-x-y）存进d中，这样如果遍历到某个y在d中，则对应的z(即-x-y)一定在d中，而且是nums[i+1:]中的元素并小于y
else:
res.add((x, -x-y, y))
return list(map(list, res))
sort & find，先排序O(NlogN)，枚举x作为第一个元素，在剩下的数组里去找y和z，即两边往中间夹。O(N2)，不需要额外空间。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
res = []
nums.sort()
n = len(nums)
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]: # 去重，如果第一个数相同，跳过
continue
l, r = i+1, n-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r])) # 记录解
# 去重，如果第二、第三个数相同，也跳过
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
# 继续找可能的解
l += 1
r -= 1
return res
18.四数之和 https://leetcode-cn.com/problems/4sum/
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
解：
和三数之和思路基本一致，固定两个数，去找后两个数。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
nums.sort() # 先排序一下，便于判重
res = set()
n = len(nums)
for i in range(n-3):
if i >0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
d = {}
for z in nums[j+1:]:
if not z in d:
d[target-nums[i]-nums[j]-z] = 1
else:
res.add((nums[i], nums[j], target-nums[i]-nums[j]-z, z))
return list(map(list, res))
由于外层有两层嵌套，可以判重之后考虑做一下剪枝
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
res = []
nums.sort()
n = len(nums)
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]: # 去重，如果第一个数相同，跳过
continue
# 剪枝，如果当前的x与剩下最小三个数之和大于target 或 与最大三个数之和小于target，跳过
if nums[i]+sum(nums[i+1:i+4]) > target or nums[i]+sum(nums[-3:]) < target:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]: # 去重，如果第一个数相同，跳过
continue
if nums[i]+nums[j]+sum(nums[j+1:j+3]) > target:
continue
if nums[i]+nums[j]+sum(nums[-2:]) < target:
continue
l, r = j+1, n-1
while l < r:
s = target-nums[i]-nums[j]-nums[l]-nums[r]
if s < 0: # 左右数之和大了
r -= 1
elif s > 0:
l += 1
else:
res.append((nums[i], nums[j], nums[l], nums[r])) # 记录解
# 去重，如果第二、第三个数相同，也跳过
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
# 继续找可能的解
l += 1
r -= 1
return res
49.字母异位词分组 https://leetcode-cn.com/problems/group-anagrams/
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
解：
#242的扩展，注意dict是unhashable的，不能作为另一个字典的key，所以这里判断是否是异位词就用sorted。O(NKlogK)
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
if len(strs) <= 1:
return [strs]
words = dict()
for s in strs:
key = tuple(sorted(s))
if not key in words:
words[key] = [s]
else:
words[key].append(s)
return list(words.values())
按小写字母计数来分类，避免用字典
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
if len(strs) <= 1:
return [strs]
words = dict()
for s in strs:
count = [0]*26
for c in s:
count[ord(c) - ord(‘a‘)] += 1 # 避免了用字典
key = tuple(count)
if not key in words:
words[key] = [s]
else:
words[key].append(s)
return list(words.values())