和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

首次提交

想法

首先第一层循环从数组num的第一个元素开始遍历i，第二层循环为维持的一个伸缩滑块，从i开始向右移动，判断滑块内的元素和与k的关系，假如左右指针之间的子数组之和小于k时，且右指针小于num长度时执行右指针+1；等于k时result计数+1并将左指针+1；大于k时只将左指针+1。直到左指针移到num最后一位。

分析

上面的想法有错误：

1. 重复计算子数组的和：可以用一个变量 current_sum 来维护当前子数组的和，避免重复计算。例如，在内层循环中（可以将时间复杂度从 $O(n^3)$ 优化到 $O(n^2)$。）：
   • 首先初始化 current_sum 为 0；
   • 每次右指针 j 移动后，将 nums[j] 加到 current_sum 中；
   • 根据 current_sum 的值进行判断。
2. 滑动窗口的逻辑问题：当前窗口内的子数组之和可能会大于等于k，但是并不意味着需要移动左指针，因为后面的数假如为负数或0仍然可能会满足和为k的要求。

代码

class Solution:
    def subarraySum(self, nums, k: int) -> int:
        result = 0
        for i in range(len(nums)):
            temp_sum = 0
            for j in range(i,len(nums)):
                temp_sum += nums[j]
                if temp_sum == k:
                    result += 1
        return result

时间复杂度

• 外层循环遍历 $n$ 个起点，内层循环最多遍历 $n-i$ 个元素（其中 $i$ 是当前起点）。
• 因此总的时间复杂度为 $O(n^2)$。

空间复杂度

• 使用了一个变量 temp_sum 来存储当前子数组的和，因此空间复杂度为 $O(1)$。

改进方向

使用 前缀和 和 哈希表，将时间复杂度优化到 $O(n)$。

代码

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        sum_dict = defaultdict(int)  # 用于记录前缀和的出现次数
        sum_dict[0] = 1  # 初始化前缀和为 0 的情况
        current_sum = 0  # 当前的前缀和

        for num in nums:
            current_sum += num  # 更新当前前缀和
            # 检查是否存在满足条件的前缀和
            if current_sum - k in sum_dict:
                result += sum_dict[current_sum - k]
            # 更新当前前缀和的出现次数
            sum_dict[current_sum] += 1
        
        return result

时间复杂度

• 遍历数组一次，每次操作（更新前缀和和哈希表查询）为 $O(1)$。
• 总时间复杂度为 $O(n)$。

空间复杂度

• 使用一个哈希表存储前缀和，最坏情况下存储 $n$ 个不同的前缀和。
• 总空间复杂度为 $O(n)$。

问题总结

错误的哈希表查询条件

result += sum_dict[current_sum]

• 问题：错误地使用了 current_sum 来查询哈希表，而不是 current_sum - k。
• 原因：current_sum 是当前的前缀和，而我应该查找的是满足 current_sum - previous_sum = k 的前缀和。换句话说，我需要判断之前是否存在一个前缀和 previous_sum，使得当前的前缀和减去它等于 $k$。

修正：

result += sum_dict[current_sum - k]

哈希表初始化问题

sum_dict[0] = 1

• 问题：我忘记了在哈希表 sum_dict 中初始化 sum_dict[0] = 1，这个初始化对于处理某些边界情况至关重要。例如，如果当前前缀和本身就等于 kkk，那么我们就需要考虑从数组开头到当前位置的子数组。
• 原因：如果不初始化 sum_dict[0] = 1，程序无法正确处理从数组的起始位置开始的和为 $k$ 的子数组。

修正：

• 确保在哈希表开始时就有 sum_dict[0] = 1。

冗余的 pre_sum 数组

• 问题：在原始代码中，我维护了一个 pre_sum 数组来存储每个位置的前缀和，这是多余的，因为我只需要一个变量来记录当前的前缀和。
• 原因：只需要一个 current_sum 变量来动态计算前缀和，而不需要额外的数组，这样能减少空间的使用。

修正：

• 直接用 current_sum 来更新当前的前缀和，并不再需要 pre_sum 数组