【LeetCode 热题 100】和为 K 的子数组

精选专栏链接 力扣 hot 100系列专栏MySQL技术笔记专栏Redis技术笔记专栏消息中间件专栏大模型专栏Python学习笔记专栏深度学习算法专栏欢迎订阅点赞关注每日精进1%与百万开发者共攀技术珠峰更多内容持续更新中~【LeetCode 热题 100】和为 K 的子数组题目描述提示信息 解题思路一暴力枚举法 暴力枚举法优化思路 什么是前缀和 解题思路二前缀和 哈希表 总结与对比题目描述给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。示例 1输入nums[1,1,1], k2输出2示例2输入nums[1,2,3], k3输出2nums [1, 2, 3] 中 长度为 1 的子数组单个元素[1] - 和为 1 不等于 3 ❌[2] - 和为 2 不等于 3 ❌[3] - 和为 3 等于 3 ✅ 找到第 1 个长度为 2 的子数组两个连续元素[1, 2] - 1 2 3 等于 3 ✅ 找到第 2 个[2, 3] - 2 3 5 不等于 3 ❌长度为 3 的子数组整个数组[1, 2, 3] - 1 2 3 6 不等于 3 ❌因此 nums [1,2,3], k 3 时和为 3 的子数组的个数为 2 。提示信息1 nums.length 2 ∗ 10 4 2 * 10^42∗104-1000 nums[i] 1000− 10 7 k 10 7 -10^7 k 10^7−107k107。核心难点这道题看似简单但有一个陷阱——数组中可能包含负数。如果数组只包含正数我们可以使用“滑动窗口”法双指针。但因为存在负数当窗口内和大于 k 时右移左指针不一定能让和变小因为左边可能是个很大的负数所以滑动窗口失效。我们需要寻找一种能够处理负数且效率更高的方法。 解题思路一暴力枚举法这道题最直观的想法是枚举所有子数组 [i, j]计算它们的和是否等于 k。暴力枚举法代码实现如下classSolution{publicintsubarraySum(int[]nums,intk){intcount0;// 外层循环枚举子数组的起始位置 ifor(inti0;inums.length;i){intsum0;// 内层循环枚举子数组的结束位置 j// 这里不需要每次重新计算 sum而是在上一次的基础上累加 nums[j]for(intji;jnums.length;j){sumnums[j];if(sumk){count;}}}returncount;}}提交代码运行结果如下复杂度分析时间复杂度为O ( N 2 ) O(N^2 )O(N2)两层 for 循环空间复杂度为 O(1) 只用了常数个变量。我们在暴力法中发现对于每一个起点 i我们都在重复计算很多中间状态的和。如果我们能利用“前缀和”把求和操作变成 O(1) 的减法能不能更快 暴力枚举法优化思路缺陷分析仔细分析就能发现暴力枚举法存在很多计算过程中的浪费。比如假设数组是 [1, 2, 3, 4]我们要找和为 9 的子数组第一轮 (i0) 我们计算了 1234 10第二轮 (i1) 我们计算了 234 9在第二轮计算 234 时计算机其实是在做重复劳动。我们在第一轮已经算过 34 了甚至在第一轮算过 234 的一部分逻辑因此暴力法的本质缺陷在于它把每一个子数组都当成了独立的个体去求和完全忽略了子数组之间是“重叠”的这一事实。它就像是一个只会死算的学生每次换一道题换一个起点 i都要从头开始按计算器而不懂得利用上一题的计算结果。优化思路如果我们能有一种方法不用重新累加而是直接通过两个“状态值”相减就能瞬间得到任意区间的和那我们就省去了内层循环的累加过程。这就是我们下面要介绍的更优解法前缀和 哈希表解法。 什么是前缀和前缀和prefix[i]表示数组从下标0到i-1的元素之和。即prefix[i] nums[0] nums[1] ... nums[i-1]。特别地我们定义 prefix[0] 0。prefixSum[0]0prefixSum[1]nums[0]prefixSum[2]nums[0] nums[1]... prefixSum[i]nums[0] nums[1]... nums[i-1] 解题思路二前缀和 哈希表为了将时间复杂度降低到 O(N) 我们需要引入前缀和并结合哈希表来查找历史状态。假设我们要找区间 [j, i] 的和等于 k。根据前缀和的定义sum(i, j)prefixSum[j1]- prefixSum[i]我们希望 sum(i, j) k即prefixSum[j1]- prefixSum[i]k变换一下公式prefixSum[i]prefixSum[j1]- k公式prefixSum[i] prefixSum[j1] - k的含义是当我们遍历到第j个元素时假设当前的累计前缀和是 curr_sum。如果我们想知道以j 结尾的、和为 k的子数组有几个我们只需要回头看之前有多少个前缀和等于 curr_sum - k如果有 1 个说明找到了 1 个子数组如果有 3 个说明以当前位置结尾的满足条件的子数组有 3 个。为了快速查找 “之前出现过多少次某个值”我们可以使用哈希表 (HashMap)。HashMap 的 Key 前缀和的值HashMap 的 Value 该前缀和出现的次数。代码实现如下classSolution{publicintsubarraySum(int[]nums,intk){// count 用于记录满足条件的子数组个数intcount0;// currSum 用于记录当前的累加前缀和intcurrSum0;// map 用于存储{前缀和数值 : 该数值出现的次数}// 为什么用 HashMap因为我们需要 O(1) 的时间查找历史前缀和HashMapInteger,IntegermapnewHashMap();// 【关键步骤】初始化前缀和为0的情况出现1次// 这解决了当 currSum 直接等于 k 时即从下标0开始的子数组无法匹配的问题map.put(0,1);for(intnum:nums){// 1. 每遍历一个新元素更新当前的前缀和currSumnum;// 2. 检查当前 map 中是否存在 (currSum - k)// 如果存在说明从那个位置到当前位置的子数组和为 kif(map.containsKey(currSum-k)){countmap.get(currSum-k);}// 3. 将当前前缀和存入 map供后续元素使用// map.getOrDefault(currSum, 0)表示尝试去 Map 里找 currSum 这个 Key// 如果找到了返回value如果没找到就返回默认值0map.put(currSum,map.getOrDefault(currSum,0)1);}returncount;}}注意千万不要漏掉map.put(0, 1);否则代码会出现如下的代码报错情况。假设 nums [3], k 3。如果不加 map.put(0, 1)初始化map {}currSum 0count 0遍历到数字 3更新前缀和currSum 0 3 3去 Map 里找目标值currSum - k 3 - 3 0找 0 这个 KeyMap 是空的没找到结果count 依然是 0。遍历结束返回 0。答案错误正确答案应该是 1提交代码运行结果如下 总结与对比方法时间复杂度空间复杂度适用场景评价暴力枚举O ( N 2 ) O(N^2)O(N2)O ( 1 ) O(1)O(1)数据量极小 (N 1000 N 1000N1000)逻辑简单但大数据量必超时。前缀和 哈希O ( N ) O(N)O(N)O ( N ) O(N)O(N)数据量大包含负数本题标准解法。用空间换时间通过数学变换将“区间和问题”转化为“查找问题”。关键点回顾不要使用滑动窗口因为有负数窗口不具备单调性Map 初始化一定要记得 map.put(0, 1)否则当子数组从第一个元素开始时会被漏掉先查后存在循环中要先检查 currSum - k 是否存在然后再把当前的 currSum 存入 Map。虽然在这道题里顺序反了也能过蛋保持“先查后存”是更严谨的逻辑习惯。