wordpress主机教程,汕头seo管理,网站的设计风格有哪些,国家企业注册信息网文章目录 方法思路#xff1a;前缀和 哈希表核心思想关键步骤 代码实现复杂度分析示例解析总结 题目描述 给定一个整数数组
nums 和一个整数
k#xff0c;请统计并返回该数组中和为
k 的子数组的数量。 子数组是数组中连续的非空元素序列。 示例
输入#xff1a;nums … 文章目录 方法思路前缀和 哈希表核心思想关键步骤 代码实现复杂度分析示例解析总结 题目描述 给定一个整数数组
nums 和一个整数
k请统计并返回该数组中和为
k 的子数组的数量。 子数组是数组中连续的非空元素序列。 示例
输入nums [1,2,3], k 3
输出2
解释子数组 [1,2] 和 [3] 满足和为 3。方法思路前缀和 哈希表
核心思想
暴力枚举所有子数组的时间复杂度为 O(n²)无法处理大规模数据。利用前缀和与哈希表的结合可以在 O(n) 时间内高效解决问题。
关键步骤 前缀和 计算到当前元素为止的前缀和 currentSum。例如遍历到第 i 个元素时前缀和为 nums[0] nums[1] ... nums[i]。 哈希表优化 哈希表 prefixSumMap 存储每个前缀和的出现次数。若存在某个前缀和 prefixSum使得 currentSum - prefixSum k则说明从 prefixSum 对应的索引之后到当前位置的子数组和为 k。通过哈希表快速查找 currentSum - k 是否存在并累加其出现次数。 初始化技巧 初始化哈希表为 {0: 1}表示前缀和为 0 出现了一次用于处理从数组起始位置到当前位置的子数组和为 k 的情况。 代码实现
import java.util.HashMap;
import java.util.Map;class Solution {public int subarraySum(int[] nums, int k) {MapInteger, Integer prefixSumMap new HashMap();prefixSumMap.put(0, 1); // 初始化前缀和为0时出现1次int currentSum 0; // 当前前缀和int result 0; // 统计结果for (int num : nums) {currentSum num; // 更新当前前缀和// 若存在前缀和为 (currentSum - k)则累加其出现次数if (prefixSumMap.containsKey(currentSum - k)) {result prefixSumMap.get(currentSum - k);}// 将当前前缀和加入哈希表并更新出现次数prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) 1);}return result;}
}复杂度分析
时间复杂度O(n)遍历数组一次。空间复杂度O(n)哈希表存储最多 n 个不同的前缀和。 示例解析
以 nums [1, 2, 3]k 3 为例
遍历元素currentSumcurrentSum - k结果累加哈希表更新111 - 3 -20{0:1, 1:1}233 - 3 00 1 1{0:1, 1:1, 3:1}366 - 3 31 1 2{0:1, 1:1, 3:1, 6:1}
结果最终 result 2对应子数组 [1,2] 和 [3]。 总结
前缀和与哈希表的结合是解决子数组和问题的经典方法适用于大规模数据。初始化哈希表为 {0:1} 是关键确保能正确统计到从数组起始位置开始的子数组。通过空间换时间将时间复杂度从 O(n²) 优化到 O(n)。
