写此系列博客的榜样来自：leetcode cookbook
复杂度
时间复杂度
- 善用指针。
若需指针遍历整个数组，可用
for x in nums:，
for i in range(1,len(nums)), for i in range(len(nums)) 中的 i 的取值范围是从 0 到 len(nums) - 1。
for i,jump in enumerate(nums):
从后往前
for i in range(n,-1,-1)
成对遍历
for x,y in pairwise(s):
空间复杂度
关键的考量就是尽量不要用新的变量，能原地修改就原地修改
思路：
- 边界条件，避免下标超出
- 返回值。设置变量时考虑其与返回值的关系，最好有实际意义，用某个变量值作为返回值
数组
数组切片
左闭右开，nums[:k]是前k个元素，nums[0],nums[1]…nums[k-1]
nums[:-k]是从第一个到倒数第k个（不包含）；nums[-k:]是最后k个
指针
快慢指针
例题26：删除有序数组中的重复项
自己做的步骤：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# double pointer
i=1
j=2
if len(nums)<=1:
return len(nums)
elif len(nums)==2:
if nums[i]==nums[i-1]:
return 1
else:
return 2
else:
while j<len(nums):
if nums[i]>nums[i-1]:
i+=1
j+=1
else:
nums[i]=nums[j]
j+=1
return i
边界条件太多，指针作用不明确，没有充分利用有序的性质
fast指针边界条件以及一直+1的性质可用for i in range(1, len(nums)):来实现（左闭右开），即
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 1
for fast in range(1,len(nums)):
if nums[fast] != nums[fast-1]:
nums[slow] = nums[fast]
slow += 1
return slow
对撞指针
接雨水42
完全懂啦！双指针很容易解决
class Solution:
def trap(self, height: List[int]) -> int:
if len(height)<=2:
return 0
l,r=0, len(height)-1
cap=0 # water capacity
hl=hr=0
while l<=r:
# 指针相向移动，互为最高柱子
hl=max(hl,height[l])
hr=max(hr,height[r])
if hl<hr: # 此时最高点肯定在该点右侧，水位等于该点以及左侧柱子高度的最大值
cap+=hl-height[l]
l+=1
else:
cap+=hr-height[r]
r-=1
return cap
分支
善于利用分支之间的互斥关系和优先级
if :
elif:
...
else:
多数问题
例题169
摩尔投票
参考 如何理解摩尔投票算法？ - 喝七喜的回答 - 知乎 https://www.zhihu.com/question/49973163/answer/235921864
摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。
实现的算法从第一个数开始扫描整个数组，有两个变量(参考第一答题者的变量名)major和count。其实这两个变量想表达的是一个“隐形的数组”array，array存储的是“当前暂时无法删除的数字”，我们先不要管major和count，只考虑这个array，同时再维护一个结果数组result，result里面存储的是每次删除一对元素之后的当前结果。
实现的算法从第一个数开始扫描整个数组，有两个变量(参考第一答题者的变量名)major和count。其实这两个变量想表达的是一个“隐形的数组”array，array存储的是“当前暂时无法删除的数字”，我们先不要管major和count，只考虑这个array，同时再维护一个结果数组result，result里面存储的是每次删除一对元素之后的当前结果。
跳跃问题
跳跃游戏55
class Solution:
def canJump(self, nums: List[int]) -> bool:
maxJump=0
for i,jump in enumerate(nums):
if maxJump<i:
return False
maxJump=max(jump+i,maxJump)
return True
跳跃游戏45
参考灵茶山艾府 链接：https://leetcode.cn/problems/jump-game-ii/solutions/2926993/tu-jie-yi-zhang-tu-miao-dong-tiao-yue-yo-h2d4/
注意：不是在无路可走的那个位置造桥，而是当发现无路可走的时候，时光倒流到能跳到最远点的那个位置造桥。换句话说，在无路可走之前，我们只是在默默地收集信息。当发现无路可走的时候，才从收集到的信息中，选择最远点造桥。所建造的这座桥的左端点（起跳位置）可能在我们当前走的这座桥的中间。
也可以理解成，当发现无路可走的时候，往回跳，选择合适的位置造桥。我们可以在最终算账的时候，把往回跳的情况擦掉，只保留往右跳，也能到达终点。所以往回跳不计入跳跃次数。
答疑 问：为什么代码只遍历到 n−2？
答：这题 n−1 是终点，nums[n−1] 这个数没有任何意义，完全可以把这个数删了，在长为 n−1 的数组上跑这个算法。或者说，遍历到 nums[n−2] 时，要么已经可以到达终点，要么需要造最后一座桥。n−1 已经是终点了，不需要造桥。
问：如果题目没有保证一定能到达 n−1，代码要怎么改？
答：见 1326. 灌溉花园的最少水龙头数目，我的题解。
加油站问题
参考灵茶山艾府 链接：https://leetcode.cn/problems/gas-station/solutions/2933132/yong-zhe-xian-tu-zhi-guan-li-jie-pythonj-qccr/
核心思路：“已经在谷底了，怎么走都是向上。”
可以有多个解但只需返回一个，于是找到最低点是最能保证一定能走完一圈的。
注意：gas 之和减去 cost 之和，对应图中复制的折线图的初始油量。如果不是负数，那么复制后的折线图的最小值，不会比第一段的最小值还小。如果是负数，那么复制后的折线图的最小值，比第一段的最小值还小，这会导致从第一段的最小值出发，行驶过程中油量会变成负数。
答疑 问：下面的代码，是否有可能算出 ans=n？
答：不会，如果最后一轮循环 s<minS，那么 s 必然小于 0，这会导致最终返回 −1。
Hash
什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
做哈希法的各种数据结构及优缺点：
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。 此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。
时间复杂度O(1)
字符串
string，同数组处理，用下标索引s[i]
同样可相加, s1+s2，完成字符串拼接
