当前位置：首页 > article >正文

Leetcode 和为 K 的子数组

article 2024/11/13 14:30:12

可以用 前缀和（Prefix Sum）和 哈希表（HashMap）来设计算法。

算法思想

前缀和的定义：
前缀和是指数组中从第一个元素开始，到当前元素为止的所有元素的总和。假设数组是 nums，定义前缀和 prefixSum[i] 为 nums[0] 到 nums[i] 的总和。即： $\text{prefixSum}[i] = \sum_{j=0}^{i} \text{nums}[j]$ 2. 前缀和之间的关系：
我们想找出数组中和为 ( k ) 的子数组。如果我们知道两个前缀和 prefixSum[i] 和 prefixSum[j]，且有：
$\text{prefixSum}[i] - \text{prefixSum}[j] = k$
那么这意味着从索引 $j + 1$ 到 $i$ 的子数组的和就是 $k$ ，也就是说，当前的子数组和正好等于 $k$ 。因此，我们的问题可以转换为：寻找是否存在之前的某个前缀和与当前前缀和的差等于 $k$ 。

一个字符串的所有前缀和（Prefix Sum）相互做差必定可以得到这个字符串的所有子数组元素和（Elements Sum）所有子数组的和都可以通过前缀和的差值来得到：无论子数组的起始位置和结束位置是什么，都可以利用前缀和的差值来快速计算出子数组的和。

哈希表存储前缀和出现的次数：
为了高效地查找前缀和的差值是否等于 $k$ ，我们使用一个哈希表 prefixSumCount。这个哈希表用于存储某个前缀和出现的次数，键是前缀和，值是该前缀和出现的次数。

当我们遍历数组时，我们不断计算当前前缀和 currentSum。我们会查看哈希表中是否存在 currentSum - k：
- 如果存在，说明有一个或者多个之前的前缀和与当前的前缀和相差 $k$ ，因此从这些前缀和对应的位置到当前索引的子数组的和就是 $k$ 。
- 每次遍历后，我们都要将当前的前缀和存入哈希表，并更新它出现的次数。
算法具体步骤：
- 初始化哈希表 prefixSumCount，并将前缀和 0 的出现次数设为 1。这样可以处理从数组开头就满足和为 $k$ 的子数组（例如，整个子数组和等于 $k$ ）。
- 定义一个变量 currentSum 用于记录当前的前缀和，以及一个变量 count 用来记录满足条件的子数组数量。
- 遍历数组 nums，对于每一个元素：
  1. 更新当前前缀和 currentSum。
  2. 检查 currentSum - k 是否存在于哈希表 prefixSumCount 中。如果存在，说明有 prefixSum[j] 满足条件，累加 count。
  3. 将当前的前缀和 currentSum 的出现次数更新到哈希表中。

举个例子

示例 1:

输入: nums = [1, 1, 1]，k = 2

遍历步骤如下：

初始化 prefixSumCount = {0: 1}，currentSum = 0，count = 0。
1. 第 1 个元素 1:
  - currentSum = 0 + 1 = 1
  - currentSum - k = 1 - 2 = -1 不在哈希表中。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1}。
2. 第 2 个元素 1:
  - currentSum = 1 + 1 = 2
  - currentSum - k = 2 - 2 = 0 在哈希表中，count += 1。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1, 2: 1}。
3. 第 3 个元素 1:
  - currentSum = 2 + 1 = 3
  - currentSum - k = 3 - 2 = 1 在哈希表中，count += 1。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1, 2: 1, 3: 1}。

最终，count = 2，表示有两个子数组的和为 2。

示例 2:

输入: nums = [1, 2, 3]，k = 3

遍历步骤如下：

初始化 prefixSumCount = {0: 1}，currentSum = 0，count = 0。
1. 第 1 个元素 1:
  - currentSum = 0 + 1 = 1
  - currentSum - k = 1 - 3 = -2 不在哈希表中。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1}。
2. 第 2 个元素 2:
  - currentSum = 1 + 2 = 3
  - currentSum - k = 3 - 3 = 0 在哈希表中，count += 1。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1, 3: 1}。
3. 第 3 个元素 3:
  - currentSum = 3 + 3 = 6
  - currentSum - k = 6 - 3 = 3 在哈希表中，count += 1。
  - 更新哈希表：prefixSumCount = {0: 1, 1: 1, 3: 1, 6: 1}。

最终，count = 2，表示有两个子数组的和为 3。

时间复杂度和空间复杂度

时间复杂度： $O (n)$ ，其中 $n$ 是数组的长度。每个元素我们只处理一次，哈希表的插入和查找操作在平均情况下是 $O (1)$ 。
空间复杂度： $O (n)$ ，主要是用于存储哈希表中的前缀和及其出现次数。

这种解法通过前缀和与哈希表的结合，能够在一次遍历中高效地解决问题，比暴力解法的 $O(n^2)$ 更加高效。

Java 实现代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        //这个哈希表的key是前缀和，value是该前缀和出现次数
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
        //前缀和 0 的出现次数需要初始化为 1，之所以为 1 是因为这使得当数组第一个元素值为 k 时，也能够正确计算。
        prefixSumMap.put(0, 1);

        //设置计数器
        int currentSum = 0; //当前前缀和
        int count = 0; //和为 k 的子数组出现次数

        //循环遍历数组
        for(int num : nums) {
            currentSum += num;

            if(prefixSumMap.containsKey(currentSum - k)) {
                count += prefixSumMap.get(currentSum - k);
            }

            //更新哈希表，将当前前缀和保存或更新。需要用HashMap的getOrDefault()
            prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
        }
        return count;
    }
}

getOrDefault 是 Java 的 HashMap 类提供的一个方法，用来获取某个键的值。如果该键存在于哈希表中，返回该键的值；如果该键不存在，则返回一个默认值。

作用：

prefixSumCount.getOrDefault(currentSum, 0) 表示：从哈希表中获取当前的前缀和 currentSum 已经出现的次数。如果 currentSum 已经存在于哈希表中，它会返回这个前缀和对应的值（出现的次数）；如果它还不存在于哈希表中，则返回默认值 0，表示该前缀和还没有出现过。

2. `+ 1`

这个 + 1 用来表示在当前前缀和 currentSum 已经被计算出来之后，更新它的出现次数。无论这个前缀和是第一次出现还是之前已经出现过，这里都需要将它的出现次数增加 1。

作用：

如果 currentSum 之前没有出现过，那么它的默认值是 0，加 1 后就表示这个前缀和现在出现了一次。
如果 currentSum 之前已经出现过，比如说它已经出现了 ( n ) 次，那么它的出现次数就会从 ( n ) 次更新为 ( n + 1 ) 次。

3. 整体作用

整体来看，这个代码片段 prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1) 的作用是：更新当前前缀和 currentSum 在哈希表中的出现次数。如果它之前出现过，就在它的出现次数上加 1；如果它之前没有出现过，就将它的值设置为 1。

查看全文

http://www.kler.cn/a/312751.html