企业官网建设流程全解析

精选专栏链接 🔗

• 力扣 hot 100系列专栏
• MySQL技术笔记专栏
• Redis技术笔记专栏
• 消息中间件专栏
• 大模型专栏
• Python学习笔记专栏
• 深度学习算法专栏

欢迎订阅，点赞＋关注，每日精进1%，与百万开发者共攀技术珠峰

更多内容持续更新中~

📝题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

示例 1：

输入：nums=[1,1,1], k=2输出：2

示例2：

输入：nums=[1,2,3], k=3输出：2

nums = [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−107<=k<=107。

核心难点：

这道题看似简单，但有一个陷阱——数组中可能包含负数。如果数组只包含正数，我们可以使用“滑动窗口”法（双指针）。但因为存在负数，当窗口内和大于 k 时，右移左指针不一定能让和变小（因为左边可能是个很大的负数），所以滑动窗口失效。我们需要寻找一种能够处理负数且效率更高的方法。

🔍 解题思路一：暴力枚举法

这道题最直观的想法是枚举所有子数组 [i, j]，计算它们的和是否等于 k。

暴力枚举法代码实现如下：

classSolution{publicintsubarraySum(int[]nums,intk){intcount=0;// 外层循环：枚举子数组的起始位置 ifor(inti=0;i<nums.length;i++){intsum=0;// 内层循环：枚举子数组的结束位置 j// 这里不需要每次重新计算 sum，而是在上一次的基础上累加 nums[j]for(intj=i;j<nums.length;j++){sum+=nums[j];if(sum==k){count++;}}}returncount;}}

提交代码，运行结果如下：

复杂度分析

• 时间复杂度为O ( N 2 ) O(N^2 )O(N2)：两层 for 循环；
• 空间复杂度为 O(1) ：只用了常数个变量。

我们在暴力法中发现，对于每一个起点 i，我们都在重复计算很多中间状态的和。如果我们能利用“前缀和”把求和操作变成 O(1) 的减法，能不能更快？

🎯 暴力枚举法优化思路

缺陷分析：

仔细分析就能发现，暴力枚举法存在很多计算过程中的浪费。比如假设数组是 [1, 2, 3, 4]，我们要找和为 9 的子数组：

• 第一轮 (i=0)： 我们计算了 1+2+3+4 = 10；
• 第二轮 (i=1)： 我们计算了 2+3+4 = 9；
• 在第二轮计算 2+3+4 时，计算机其实是在做重复劳动。我们在第一轮已经算过 3+4 了，甚至在第一轮算过 2+3+4 的一部分逻辑；

因此暴力法的本质缺陷在于：它把每一个子数组都当成了独立的个体去求和，完全忽略了子数组之间是“重叠”的这一事实。它就像是一个只会死算的学生，每次换一道题（换一个起点 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[j+1]- prefixSum[i]

我们希望 sum(i, j) == k，即：

prefixSum[j+1]- prefixSum[i]==k

变换一下公式：

prefixSum[i]==prefixSum[j+1]- k

公式prefixSum[i] == prefixSum[j+1] - k的含义是：当我们遍历到第j个元素时，假设当前的累计前缀和是 curr_sum。如果我们想知道以j 结尾的、和为 k的子数组有几个，我们只需要回头看：之前有多少个前缀和等于 curr_sum - k？

• 如果有 1 个，说明找到了 1 个子数组；
• 如果有 3 个，说明以当前位置结尾的满足条件的子数组有 3 个。

为了快速查找 “之前出现过多少次某个值”，我们可以使用哈希表 (HashMap)。

• HashMap 的 Key： 前缀和的值；
• HashMap 的 Value： 该前缀和出现的次数。

代码实现如下：

classSolution{publicintsubarraySum(int[]nums,intk){// count 用于记录满足条件的子数组个数intcount=0;// currSum 用于记录当前的累加前缀和intcurrSum=0;// map 用于存储：{前缀和数值 : 该数值出现的次数}// 为什么用 HashMap？因为我们需要 O(1) 的时间查找历史前缀和HashMap<Integer,Integer>map=newHashMap<>();// 【关键步骤】初始化前缀和为0的情况出现1次// 这解决了当 currSum 直接等于 k 时（即从下标0开始的子数组）无法匹配的问题map.put(0,1);for(intnum:nums){// 1. 每遍历一个新元素，更新当前的前缀和currSum+=num;// 2. 检查当前 map 中是否存在 (currSum - k)// 如果存在，说明从那个位置到当前位置的子数组和为 kif(map.containsKey(currSum-k)){count+=map.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 = 0，count = 0；

• 遍历到数字 3：

  • 更新前缀和：currSum = 0 + 3 = 3；
  • 去 Map 里找目标值：currSum - k = 3 - 3 = 0；
  • 找 0 这个 Key：Map 是空的，没找到；
  • 结果：count 依然是 0。

• 遍历结束，返回 0。（答案错误！正确答案应该是 1）

提交
代码，运行结果如下：

🧩 总结与对比

关键点回顾：

• 不要使用滑动窗口：因为有负数，窗口不具备单调性；
• Map 初始化：一定要记得 map.put(0, 1)，否则当子数组从第一个元素开始时会被漏掉；
• 先查后存：在循环中，要先检查 currSum - k 是否存在，然后再把当前的 currSum 存入 Map。虽然在这道题里顺序反了也能过，蛋保持“先查后存”是更严谨的逻辑习惯。