LeetCode 560 & 303：前缀和思想解析**

LeetCode 560 & 303：前缀和思想解析

🔥 LeetCode 560. 和为 K 的子数组

📌 题目描述

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

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

💡 解题思路

这道题的关键点是利用 前缀和 + 哈希表 进行优化，使其达到 O(n) 复杂度。

🚀 前缀和的核心思想

• 设 cur_sum 为当前的前缀和。
• 目标是寻找 cur_sum - k 之前出现的次数。
• 维护一个哈希表 pre_sum 记录所有前缀和出现的次数。
• 每次 cur_sum 更新时，检查 pre_sum[cur_sum - k] 以统计所有符合条件的子数组。

🔗 代码实现

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre_sum = defaultdict(int)
        pre_sum[0] = 1  # 初始化，表示前缀和为 0 出现 1 次
        
        cur_sum, res = 0, 0
        for num in nums:
            cur_sum += num  # 更新当前前缀和
            res += pre_sum[cur_sum - k]  # 统计之前出现的 (cur_sum - k) 次数
            pre_sum[cur_sum] += 1  # 记录当前前缀和的出现次数
        
        return res

📊 时间复杂度分析

• 时间复杂度 ： O(n) ，遍历一次数组，每次操作均为 O(1) 。
• 空间复杂度 ： O(n) ，哈希表存储前缀和。

📝 示例解析

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

• pre_sum = {0:1, 1:1, 2:1, 3:1}
• 计算过程：
  • cur_sum = 1 → pre_sum[1 - 2] = pre_sum[-1] 不存在 → res = 0
  • cur_sum = 2 → pre_sum[2 - 2] = pre_sum[0] = 1 → res = 1
  • cur_sum = 3 → pre_sum[3 - 2] = pre_sum[1] = 1 → res = 2

这道题的技巧在于 快速找到前缀和满足 cur_sum - k 的子数组 ，实现 O(n) 级别的快速查找！

🚀 LeetCode 303. 区域和检索 - 数组不可变

📌 题目描述

给定一个整数数组 nums ，实现 sumRange(left, right) 来计算 索引 left 和 right 之间（包含左右端点）的元素总和 。

💡 解题思路

• 前缀和优化查询 ：
  • 预计算前缀和 s[i] ，其中 s[i] 代表 nums 前 i 个元素的和 。
  • sumRange(left, right) = s[right+1] - s[left] 。

🔗 代码实现

from typing import List

class NumArray:
    def __init__(self, nums: List[int]):
        s = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + x  # 计算前缀和
        self.s = s
    
    def sumRange(self, left: int, right: int) -> int:
        return self.s[right + 1] - self.s[left]  # 利用前缀和计算子数组和

📊 时间复杂度分析

• 初始化 ： O(n) （计算前缀和）。
• 查询 sumRange ： O(1) （直接相减即可）。

📝 示例解析

输入:
nums = [-2, 0, 3, -5, 2, -1]
obj = NumArray(nums)
obj.sumRange(0, 2)  # 输出: 1  (-2 + 0 + 3 = 1)
obj.sumRange(2, 5)  # 输出: -1 (3 + (-5) + 2 + (-1) = -1)
obj.sumRange(0, 5)  # 输出: -3 (-2 + 0 + 3 + (-5) + 2 + (-1) = -3)

🎯 重点总结

560. 和为 K 的子数组（前缀和 + 哈希表）

✅ 问题： 统计子数组和为 k 的个数。

✅ 优化方法： 使用 哈希表 pre_sum 记录前缀和，快速查找 cur_sum - k 的次数。

✅ 时间复杂度： O(n)

✅ 空间复杂度： O(n)

303. 区域和检索（前缀和优化查询）

✅ 问题： 计算区间 [left, right] 的元素总和。

✅ 优化方法： 预计算 前缀和 ，查询时 O(1) 复杂度。

✅ 时间复杂度： O(n) 预计算， O(1) 查询。

✅ 空间复杂度： O(n)

两道题都利用了 前缀和思想 ，掌握这个技巧，你将更轻松地应对数组子区间和相关问题！🔥🚀