每日算法学习记录 - 250602

今天学习和复习了两道利用前缀和与哈希表解决的子数组问题，特此记录。

560. 和为 K 的子数组

题目

思路

本题的核心思想是利用 前缀和 与 哈希表 来优化查找过程。

解题过程

题目要求统计和为 k 的子数组个数。

1. 我们首先预处理出一个前缀和数组 prefix，其中 prefix[i] 表示原数组 nums 中区间 [0, i-1] 的元素之和。特别地，prefix[0] = 0。
2. 对于任意子数组 nums[i...j-1] (假设 j > i)，其和可以表示为 prefix[j] - prefix[i]。
3. 我们目标是找到满足 prefix[j] - prefix[i] = k 的 (i, j) 对的个数。
4. 将上式变形，得到 prefix[i] = prefix[j] - k。
5. 我们可以遍历计算出的 prefix 数组（从 prefix[0] 到 prefix[n]，其中 n 是 nums 的长度）。当遍历到 prefix[j]（在代码中用变量 x 表示）时，我们希望在 之前已经遇到过 的前缀和中查找是否存在一个 prefix[i]，使得 prefix[i] == prefix[j] - k。
6. 使用一个哈希表 map 来存储已经遍历过的前缀和 sum_val 及其出现的次数 count (即 map<sum_val, count>)。
7. 当我们遍历 prefix 数组，对于当前的元素 x (它代表一个 prefix[j])

这样，通过一次遍历，我们就能统计出所有和为 k 的子数组数量。

复杂度

• 时间复杂度: $O(N)$，其中 $N$ 是数组 nums 的长度。计算前缀和数组需要 $O(N)$，遍历前缀和数组并操作哈希表（插入和查找平均 $O(1)$）也需要 $O(N)$。
• 空间复杂度: $O(N)$，主要用于存储前缀和数组和哈希表。在最坏情况下，哈希表可能存储 $N+1$ 个不同的前缀和。

Code

class Solution {public int subarraySum(int[] nums, int k) {int ret = 0, n = nums.length;int[] prefix = new int[n + 1];Map<Integer, Integer> map = new HashMap<>(n + 1);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}for (int x : prefix) {int key = x - k;ret += map.getOrDefault(key, 0);map.put(x, map.getOrDefault(x, 0) + 1);}return ret;}
}

930. 和相同的二元子数组（复习）

题目

说明

这道题是复习题。之前使用过滑动窗口的解法（可参考 每日算法-250404），本次采用与上一题 (560. 和为 K 的子数组) 类似的 前缀和 + 哈希表 思路。

由于解题逻辑与上一题高度一致（只是目标和从 k 变成了 goal），这里不再赘述详细过程，仅列出代码实现。核心都是计算前缀和，然后查找 current_prefix_sum - goal 是否在哈希表中出现过。

代码

class Solution {public int numSubarraysWithSum(int[] nums, int goal) {int ret = 0, n = nums.length;int[] prefixSum = new int[n + 1];Map<Integer, Integer> map = new HashMap<>(n + 1);for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}for (int x : prefixSum) {int key = x - goal;ret += map.getOrDefault(key, 0);map.put(x, map.getOrDefault(x, 0) + 1);}return ret;}
}