1. 两数之和
560. 和为 K 的子数组
1248. 统计「柔美子数组」
437. 门路总和 III
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目难度: Easy
对于第一次接触这种类型的题目的人而言, 最能想到的形式就是相似冒泡排序的暴力算法, 工夫复杂度为 $O(n^2)$, 空间复杂度为 $O(1)$.
但题目要求每一个元素只能应用一次, 显然下面的做法并不能满足要求, 那么怎么才能够每个元素只应用一次呢
回到最直观的想法, 咱们须要两两元素进行判断: nums[i] + nums[j] = target?, 如果每个元素只能应用一次, 换一种思路, nums[j] = target – nums[i], 能够想到将 target – nums[i]提前保留下来 因为本题返回的是索引, 于是天然想到应用字典来保留, 后续只有判断 nums[j]是否在字典中就能够了.
顺着思路, 能够写出如下的代码
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums or len(nums) < 2:
return
# 应用字典保留 target - nums[i]
prefix_sum = {}
n = len(nums)
for i in range(n):
if nums[i] in prefix_sum:
return [prefix_sum[nums[i]], i]
prefix[target-nums[i]] = i
工夫复杂度 $O(n)$, 空间复杂度 $O(n)$
560. 和为 K 的子数组
给定一个整数数组和一个整数 k，你须要找到该数组中和为 k 的间断的子数组的个数。
示例 1 :
输出:nums = [1,1,1], k = 2
输入: 2 , [1,1] 与 [1,1] 为两种不同的状况。
阐明 :
数组的长度为 [1, 20,000]。
数组中元素的范畴是 [-1000, 1000]，且整数 k 的范畴是 [-1e7, 1e7]。
一开始看到这个题目, 的确不知如何下手, 次要问题在于:
- 子数组中可能蕴含正数.
- 并没有限定子数组长度.
现假如子数组开始地位为 $i$, 完结地位为 $j$, 即 $nums[i]+…+nums[j]=target$
而
$nums[i]+…+nums[j]=sum(nums_{0,…,j})-sum(nums_{0,…,i-1})$
因而, 咱们能够用一个字典保留所有可能的间断子数组 (上式中左边局部) 和, 字典的值为和等于 k 的子数组个数.
这样, 能够一次遍历, 即可失去和为 k 的所有子数组个数.
依照这个思路, 能够写出如下的代码
def subarraySum(nums, k):
if not nums:
return 0
n = len(nums)
res = 0
# 从索引为 0 的地位到以后地位的数组和
prefix_sum = 0
# 保留了所有前缀和及其对应的子数组个数
dicts = {0: 1}
for i in range(n):
prefix_sum += nums[i]
if prefix_sum - k in dicts:
res += dicts[prefix_sum - k]
#
dicts[prefix_sum] = dicts.get(prefix_sum, 0) + 1
return res
工夫复杂度 $O(n)$, 空间复杂度 $O(n)$
1248. 统计「柔美子数组」
给你一个整数数组 nums 和一个整数 k。
如果某个 间断 子数组中恰好有 k 个奇数数字，咱们就认为这个子数组是「柔美子数组」。
请返回这个数组中「柔美子数组」的数目。
示例 1：
输出：nums = [1,1,2,1,1], k = 3
输入：2
解释：蕴含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1]。
示例 2：
输出：nums = [2,4,6], k = 1
输入：0
解释：数列中不蕴含任何奇数，所以不存在柔美子数组。
示例 3：
输出：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输入：16
提醒：
- 1 <= nums.length <= 50000
- 1 <= nums[i] <= 10^5
- 1 <= k <= nums.length
该题和上一题 (560 题) 的思路基本一致, 只是由元素和变为了奇数个数, 实质上都是一样的.
def numberOfSubarrays(nums, k):
if not nums or len(nums) < k:
return 0
res = 0
# 值示意所有可能的奇数个数, 及其对应的子数组的个数
dicts = {0: 1}
# 示意从索引为 0 的地位到以后地位, 奇数的个数
prefix_sum = 0
n = len(nums)
for i in range(n):
if nums[i] % 2:
prefix_sum += 1
if prefix_sum - k in dicts:
res += dicts[prefix_sum - k]
if prefix_sum not in dicts:
dicts[prefix_sum] = 0
# 奇数个数为 prefix_sum 的子数组个数加 1
dicts[prefix_sum] += 1
return res
工夫复杂度 $O(n)$, 空间复杂度 $O(n)$
437. 门路总和 III
给定一个二叉树，它的每个结点都寄存着一个整数值。
找出门路和等于给定数值的门路总数。
门路 不须要从根节点开始，也不须要在叶子节点完结，然而门路方向必须是向下的（只能从父节点到子节点）。
二叉树不超过 1000 个节点，且节点数值范畴是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的门路有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
这题能够看作是前缀和在二叉树中的利用, 思路还是一样的
def pathSum(self, root, sum):
self.dicts = {0: 1}
self.res = 0
def helper(root, prefix_sum, sum):
if not root:
return 0
prefix_sum += root.val
if prefix_sum - sum in self.dicts:
self.res += self.dicts[prefix_sum - sum]
self.dicts[prefix_sum] = self.dicts.get(prefix_sum, 0) + 1
helper(root.left, prefix_sum, sum)
helper(root.right, prefix_sum, sum)
# Note: 回到上一层时, 须要将以后的前缀和对应的门路数目减 1
self.dicts[prefix_sum] -= 1
helper(root, 0, sum)
return res 工夫复杂度 $O(n)$, 空间复杂度 $O(n)$
总结
前缀和的办法通常用于解决序列中满足条件的 间断 子序列的数目, 对于这类问题, 通常会应用字典来记录每个前缀和及其呈现的次数, 这样每次只须要判断(以后前缀和 – target) 是否在字典中, 如果在, 则后果加上该前缀和对应的个数. 否则将其增加到字典中.
值得注意的是, 前缀和字典通常会初始化为{0, 1}, 因为如果满足条件的间断子数组是从 0 开始时, 以后前缀和等于间断子数组和, (以后前缀和 – target) = 0 并不一定存在字典中.
以上内容, 如有谬误或不当之处, 能够间接在评论区指出. 恳请赐教, 谢谢.