LeetCode第11天（四） huawei 测试题 前缀和

以下题目来源力扣
724. 寻找数组的中心下标
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

class Solution:def pivotIndex(self, nums: List[int]) -> int:for i in range(0,len(nums)):if sum(nums[0:i])==sum(nums[i+1:]):return i return -1

560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:#超时了pre=[0]*(len(nums)+1)pre[0]=0#nums[0]count=0for i in range(0,len(nums)):pre[i+1]=pre[i]+nums[i]# print(pre)for i in range(len(nums)+1):for j in range(i+1,len(nums)+1):if pre[j]-pre[i]==k:count=count+1return count

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:pre_sum_map = {0:1}  #利用字典记录不同前缀和的个数pre_sum = 0  count = 0  for num in nums: pre_sum += num if pre_sum - k in pre_sum_map:  count += pre_sum_map[pre_sum - k]if pre_sum in pre_sum_map:  pre_sum_map[pre_sum] += 1else:  #pre_sum_map[pre_sum] = 1return count

437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:count=0def dfs(root,targetSum):if root==None:return 0res=0if root.val==targetSum:res=res+1res+=dfs(root.left,targetSum-root.val)res+=dfs(root.right,targetSum-root.val)return resif root==None:return 0res = dfs(root, targetSum)res += self.pathSum(root.left, targetSum)res += self.pathSum(root.right, targetSum)return res

1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:def is_qishu(num):if num%2!=0:return 1else: return 0pre={0:1}sum_=0count=0for i in range(0,len(nums)):sum_=sum_+is_qishu(nums[i])if sum_-k in pre:count=count+pre[sum_-k]if sum_ in pre:pre[sum_]+=1else:pre[sum_]=1return count