哈希算法题目：和为K的子数组 题目描述 给定一个整数数组 nums 和一个整数 k ，你需要统计并返回该数组中"和为 k 的连续子数组"的个数。例如： 输入： nums = [1,1,1] , k = 2 输出： 2 （子数组 [1,1] 出现两次，分别对应索引 [0,1] 和 [1,2] ） 解题思路 暴力解法（不推荐） ： 枚举所有子数组的起点和终点，计算每个子数组的和，统计和等于 k 的数量。 时间复杂度：O(n²)，效率低。 前缀和 + 哈希表优化 ： 核心思想 ：定义 prefix_sum[i] 为数组前 i 项的和，则子数组 [j, i] 的和为 prefix_sum[i] - prefix_sum[j-1] 。若该差值为 k ，即说明子数组和为 k 。 转化问题 ：对于每个 i ，需统计有多少个 j 满足 prefix_sum[j-1] = prefix_sum[i] - k 。 哈希表作用 ：用哈希表记录每个前缀和出现的次数，遍历时直接查询 prefix_sum[i] - k 的出现次数，累加至结果。 逐步推导 初始化 ： 哈希表 sum_count 记录前缀和的出现次数，初始时 sum_count[0] = 1 （因为空子数组的前缀和为 0）。 变量 current_sum 记录当前前缀和， result 统计结果。 遍历数组 ： 对于每个元素 nums[i] ，更新 current_sum += nums[i] 。 检查 current_sum - k 是否在哈希表中：若存在，则 result += sum_count[current_sum - k] 。 将 current_sum 的出现次数存入哈希表。 示例演算 （ nums = [1,1,1], k = 2 ）： 初始： current_sum = 0 , sum_count = {0:1} , result = 0 i=0: current_sum = 1 ，查 1-2=-1 不在表中， sum_count[1] = 1 i=1: current_sum = 2 ，查 2-2=0 在表中（出现1次）， result += 1 ， sum_count[2] = 1 i=2: current_sum = 3 ，查 3-2=1 在表中（出现1次）， result += 1 ， sum_count[3] = 1 最终 result = 2 。 关键点 哈希表将查询时间降至 O(1)，整体时间复杂度优化至 O(n)。 注意处理前缀和为 0 的初始状态，避免遗漏从数组开头开始的子数组。 总结 通过前缀和与哈希表的结合，将问题转化为"两数之差"的统计问题，高效解决了子数组和统计的难题。