所有题目来源于LeetCode
1、哈希
1.1 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
example:
输入：nums = [2,7,11,15]，target = 9
输出：[0,1]
class Solution(object):
def twoSum(self, nums, target):
hashTable = dict()
for i,v in enumerate(nums):
if target - v in hashTable:
return i, hashTable[target - v]
hashTable[v] = i1.2 字母异位词分组
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。
example：
输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
class Solution(object):
def groupAnagrams(self, strs):
hashTable = dict()
for key in strs:
val="".join(sorted(key))
hashTable[val]=hashTable.get(val,[])+[key]
return hashTable.values()1.3 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
example：
输入：nums = [100,4,200,1,3,2]
输出：4
class Solution(object):
def longestConsecutive(self, nums):
nums = set(nums)
maxLength=0
for num in nums:
if num-1 not in nums:
startNumber = num+1
length=1
while startNumber in nums:
length+=1
startNumber+=1
maxLength=max(maxLength,length)
return maxLength2、双指针
2.1 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
example：
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]
class Solution(object):
def moveZeroes(self, nums):
slow=0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow],nums[fast]=nums[fast],nums[slow]
slow+=1
return nums2.2 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
题解：指针移动由最短边决定，无论长边移动后高度增加或者减少，都只能是装水量变少。
# 双指针
nums = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left = 0
right = len(nums) - 1
maxContainer = 0
while left != right:
if nums[left] <= nums[right]:
maxContainer = max(maxContainer, (right - left) * nums[left])
left += 1
else:
maxContainer = max(maxContainer, (right - left) * nums[right])
right -= 1
print(maxContainer) # 492.3 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
example：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
# 三数之和 a+b+c=0
nums = [-1, 0, 1, 2, -1, -4]
nums = sorted(nums)
arr = list()
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
target = -nums[i]
end = n - 1
for start in range(i + 1, n):
if start > i + 1 and nums[start] == nums[start - 1]:
continue
while start < end and nums[start] + nums[end] > target:
end -= 1
if start == end:
break
if nums[start] + nums[end] == target:
arr.append([nums[i], nums[start], nums[end]])
print(arr) # [[-1, -1, 2], [-1, 0, 1]]2.4 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
方法：使用单调栈。找到中间凹槽位置，并利用单调栈找出其左边的第一个最高柱子，右边的第一个最高柱子即循环遍历到的这一个元素。
# 单调栈（单增栈）
# 若当前遍历元素大于栈顶元素，则出现凹槽
height = [4, 2, 0, 3, 2, 5]
list = []
s = 0
for i, v in enumerate(height):
while list and v > height[list[-1]]:
top = list.pop()
if list:
left = list[-1]
wid = i - left - 1
hei = min(height[left], height[i]) - height[top]
s += wid * hei
else:
break
list.append(i)
print(s) # 93、滑动窗口
3.1 无重复字符的最长子串
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
example：
输入：s = "abcabcbb"
输出：3
s = 'abcabcbb'
left, right, length, max_length = 0, 0, 0, 0
hashTable = set()
while right < len(s):
if s[right] not in hashTable:
hashTable.add(s[right])
right += 1
length += 1
if length > max_length:
max_length = length
else:
while s[right] in hashTable:
hashTable.remove(s[left])
left += 1
length -= 1
hashTable.add(s[right])
right += 1
length += 1
print(max_length) # 33.2 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
example：
输入：s = "abab"，p = "ab"
输出：[0,1,2]
# 找到字符串中所有字母异位词
s = "cbaebabacd"
p = "abc"
record = []
hashTable = dict()
for k in range(26):
hashTable[k] = 0
for i in p:
hashTable[ord(i) - ord('a')] += 1
left = right = 0
length = len(s)
while right < length:
hashTable[ord(s[right]) - ord('a')] -= 1
while hashTable[ord(s[right]) - ord('a')] < 0:
hashTable[ord(s[left]) - ord('a')] += 1
left += 1
if right - left + 1 == len(p):
record.append(left)
right += 1
print(record) # [0, 6]
