网站ie兼容性差,软件搭建平台,宁波电器网站制作,玩家世界网站建设LeetCode-560. 和为 K 的子数组【数组 哈希表 前缀和】 题目描述#xff1a;解题思路一#xff1a;一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数#xff0c;那么和为k的子数组的个数就是当前前缀和-k的个数#xff0c;即preSums[presum - k]。画个图表述就是解题思路一一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数那么和为k的子数组的个数就是当前前缀和-k的个数即preSums[presum - k]。画个图表述就是解题思路二解题思路三 题目描述
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2 输出2 示例 2
输入nums [1,2,3], k 3 输出2
提示
1 nums.length 2 * 104 -1000 nums[i] 1000 -107 k 107
解题思路一一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数那么和为k的子数组的个数就是当前前缀和-k的个数即preSums[presum - k]。画个图表述就是 红色的是当前遍历到的前缀和presum假如他之前有两个前缀和等于presum−k蓝色范围那么很明显就会有两个连续子数组的和为k对应图中橙色范围。
【这里利用了collections.defaultdict(int)的特性可以直接赋值并且不存在的key对应的value为0】
class Solution:def subarraySum(self, nums: List[int], k: int) - int:count 0n len(nums)preSums collections.defaultdict(int)preSums[0] 1 # 这个初始化很重要presum 0for i in range(n):presum nums[i]count preSums[presum - k] # 利用defaultdict的特性当presum-k不存在时返回的是0。这样避免了判断preSums[presum] 1 # 给前缀和为presum的个数加1return count时间复杂度O(n) 空间复杂度O(n) 很巧妙
解题思路二 时间复杂度O(n) 空间复杂度O(n)
解题思路三 时间复杂度O(n) 空间复杂度O(n)
