classSolution:defsubarraySum(self, nums: List[int], k:int)->int:
presum =[0]*(len(nums)+1)for i, x inenumerate(nums):
presum[i +1]= presum[i]+ x
ans =0
cnt = defaultdict(int)for p in presum:
ans += cnt[p - k]# 满足p2-k = p1的个数
cnt[p]+=1return ans
二、236. 二叉树的最近公共祖先
代码:
classSolution:deflowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode)-> TreeNode:if root in(None, p, q):return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)if left and right:# 左右都找到return root # 当前节点是最近公共祖先return left or right
三、124. 二叉树中的最大路径和
代码:
classSolution:defmaxPathSum(self, root: Optional[TreeNode])->int:
ans =-inf
defdfs(node: Optional[TreeNode])->int:if node isNone:return0# 没有节点,和为 0
l_val = dfs(node.left)# 左子树最大链和
r_val = dfs(node.right)# 右子树最大链和nonlocal ans
ans =max(ans, l_val + r_val + node.val)# 两条链拼成路径returnmax(max(l_val, r_val)+ node.val,0)# 当前子树最大链和(注意这里和 0 取最大值了)
dfs(root)return ans