哈希算法题目：和为K的子数组 我们先明确题意：给你一个整数数组 nums 和一个整数 k ，你需要统计并返回该数组中和为 k 的连续子数组的个数。 举个例子： 输入：nums = [ 1,1,1 ], k = 2 输出：2 解释：连续子数组 [ 1,1] 出现在位置 [ 0,1] 和 [ 1,2 ]，所以是 2 个。 第一步：暴力枚举（基础思路） 最直接的思路是枚举所有可能的子数组，然后计算它们的和，看是否等于 k 。 外层循环 i 从 0 到 n-1，表示子数组的起始位置。 内层循环 j 从 i 到 n-1，表示子数组的结束位置。 在 j 移动过程中，累加 nums[j] 得到子数组 nums[i..j] 的和，判断是否等于 k 。 这种方法的时间复杂度是 O(n²)，在数组较长时会超时。 第二步：前缀和优化（降低时间复杂度） 我们可以提前计算“前缀和”，定义 prefix[i] 表示 nums[0] + nums[1] + ... + nums[i-1] （即前 i 个元素的和， prefix[0] = 0 ）。 那么子数组 nums[i..j] 的和就等于 prefix[j+1] - prefix[i] 。 于是问题转化为：寻找有多少对 (i, j) ，满足 i < j 且 prefix[j] - prefix[i] = k 。 这仍然是一个 O(n²) 的思路（固定 j，枚举所有 i <j），但我们可以进一步优化。 第三步：哈希表优化（O(n) 解法） 将条件 prefix[j] - prefix[i] = k 改写为 prefix[i] = prefix[j] - k 。 当我们遍历数组，计算到位置 j 时， prefix[j] 是已知的。我们只需要知道在 j 之前，有多少个位置 i 满足 prefix[i] = prefix[j] - k 。 这可以用一个哈希表（字典/映射）来记录之前出现过的各个前缀和值及其出现次数。 算法步骤 ： 初始化哈希表 prefix_sum_count ，键是前缀和，值是该前缀和出现的次数。初始时放入 {0: 1} ，表示前缀和为 0 出现 1 次（即一个元素都不取的情况）。 初始化 current_sum = 0 表示当前前缀和， count = 0 表示满足条件的子数组个数。 遍历数组 nums 中的每个数 num ： 更新当前前缀和： current_sum += num 。 计算我们需要的前缀和： need = current_sum - k 。 在哈希表中查找 need 出现的次数，累加到 count 中。 将当前前缀和 current_sum 在哈希表中的计数加 1。 遍历结束后返回 count 。 为什么初始时 {0: 1} 是必要的？ 考虑子数组从第一个元素开始的情况，比如 nums[0] + nums[1] = k ，那么到索引 1 时， current_sum - k 应该等于 0。如果没有初始化 0:1 ，这种情况就会被漏掉。 第四步：举例说明 以 nums = [1, 1, 1] , k = 2 为例： 初始化： prefix_sum_count = {0:1} , current_sum = 0 , count = 0 第 1 步： num = 1 current_sum = 1 need = 1 - 2 = -1 ，哈希表中没有 -1， count += 0 （不变） 更新哈希表： {0:1, 1:1} 第 2 步： num = 1 current_sum = 2 need = 2 - 2 = 0 ，哈希表中 0 出现次数为 1， count += 1 → count = 1 （对应子数组 [ 1,1 ]，前两个元素） 更新哈希表： {0:1, 1:1, 2:1} 第 3 步： num = 1 current_sum = 3 need = 3 - 2 = 1 ，哈希表中 1 出现次数为 1， count += 1 → count = 2 （对应子数组 [ 1,1 ]，后两个元素） 更新哈希表： {0:1, 1:1, 2:1, 3:1} 结果：2，符合预期。 第五步：时间复杂度与空间复杂度 时间复杂度：O(n)，只遍历一次数组，每次哈希操作 O(1)。 空间复杂度：O(n)，最坏情况下不同的前缀和数量为 n+1 个。 第六步：扩展思考 这种方法可以扩展到“和为 k 的子数组”的变种问题，比如： 统计和为 k 的子数组的最长长度（哈希表记录前缀和第一次出现的索引）。 数组中含有负数时也适用（因为哈希表不依赖有序性）。 如果要求子数组个数满足“和是 k 的倍数”等条件，思路类似但需调整哈希表的键（例如存储前缀和对 k 取模的结果）。 核心 ：通过前缀和将子数组和问题转化为两数之差问题，再利用哈希表存储历史信息，避免双重循环。