0x3f第二天复习（9：50-11：20）
1.先把昨天学习的代码敲一遍
四个题：分别记录时间
1两数之和 6min
class Solution:
def twoSum(self, nums:List[int], target:int ) -> List[int]:
nums.sort()
n = len(nums)
left = 0
right = n - 1
while left < right:
if nums[left] + nums[right] == target:
break
elif nums[left] + nums[right] < target:
left += 1
else:
right -= 1
return [left,right]
潜在问题：sort的引用想了半天也不确定，凭感觉写的num.sort()
nums[left] + nums[right]写了多遍，把他提前，加上参数，简略
错误：0x3f可以sort但是力扣这个题不行，因为力扣要返回原顺序，要用哈希表
没有考虑无解的情况，我这个代码，如果无解，还是会输出
把return放到==里面，在while之外再加一个return[]返回空列表
2.三数之和 20min
class Solution:
def threeSum(self, nums:List[int]) -> List[List[int]]:
n = len(nums)
ans = []
nums.sort()
for i in range(n-2):
target = nums[i]
#i不重复
if i>0 and target == nums[i-1]:
continue
if target + nums[i+1] + nums[i+2] > 0 :
break
if target + nums[-1] + nums[-2] < 0:
continue
j = i + 1
k = n - 1
while j < k :
s = target + nums[j] + nums[k]
if s == 0:
ans.append([target,nums[j],nums[k]])在这找到解，处理jk
return ans ×
elif s < 0:
while j<k and nums[j] == nums[j+1]:
j += 1
else:
while k<j and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
return []
问题：
去除jk的重复逻辑混乱，在循环的哪个地方没有弄对，应该是在找到解的循环处，进行去除
没写sort
return的位置有大问题，像这种多个解的情况，return就不能在循环里，绝对在循环的最外面，因为只要已完成return语句，直接就结束了循环
return []的意义是什么？？
核心代码重敲：
if s== 0:
ans.append([target,nums[j],nums[k]])
while j<k and nums[j] == nums[j+1]:
j+=1
while k>j and nums[k] == nums[k-1]:
k-=1
j+=1 改的时候还是没写
k-=1
if s <0:
j+=1
if s>0:
k-=1
3水桶 5min
4.接水
方法一：最大前缀最大后缀数组 10min
class Solution:
def trap(self, height:List[int])->int:
#核心思想，木桶原则，只考虑短的木板，视为单个木桶，接水量为min（最大前缀，最大后缀）-底部高度
#引入数组，记录每个单位的最大前缀最大后缀
n = len(height)
ans = 0
pre_max = [0]*n
suf_max = [0]*n
pre_max[0] = height[0]
suf_max[-1] = height[-1]
#遍历得到每个最大前缀
for i in range(1,n):
pre_max[i] = max(pre_max[i],pre_max[i-1])需对比height[i]和pre_max[i-1]。
#遍历得到每个最大后缀
for i in range(n-2,-1,-1):
suf_max[i] = max(suf_max[i],suf_max[i+1])需对比height[i]和suf_max[i+1]。
for i in range(n):
ans += min(pre_max[i],suf_max[i])-height[i]
return ans
方法二：最大前缀最大后缀指针
能想到大体思路，但是最关键的点还是没想到
那就是当pre_max < suf_max的时候，不管你右边的指针指在哪，反正pre_max肯定比你小了，就可以计算pre_max，也就是当前左指针指的水桶的接水量了，也就是pre_max - height[left]，然后就更新left，也就是当前left的最大前缀
另一侧同理
这就是最重要的一个思想，这就是为什么几行代码就能完成，就是靠的这个思想
核心语句：
对于右侧来说，你有可能还能变大，但我已经比你小了，对我左侧已经够了，我只需要知道premax，我就能求接水量了
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max:
if pre_max < suf_max: