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 -> 32. 5 -> 2 -> 13. -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 并不一定存在字典中.
以上内容, 如有谬误或不当之处, 能够间接在评论区指出. 恳请赐教, 谢谢.