DSA Interview Prep · 课时

前缀和与累计总和

Q: 「前缀和与累计总和」课时是免费的吗？

是的 — 「前缀和与累计总和」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 「前缀和与累计总和」这节课中我会学到什么？

构建前缀和数组，以 O(1) 的时间回答区间求和查询，并将该技术应用于最大和子数组等问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

Q: 「前缀和与累计总和」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

构建前缀和数组，以 O(1) 的时间回答区间求和查询，并将该技术应用于最大和子数组等问题。

前缀和与累计总和 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

区间和问题

给定一个数组 nums，您需要回答许多这类查询：索引 i 到索引 j 的元素之和是多少？朴素地计算每个查询需要 O(n) 时间，因此 k 个查询需要 O(n×k) 时间。使用前缀和数组时，可以先在 O(n) 时间内预计算累计和，然后在 O(1) 时间内回答每个查询。这是面试中最广泛使用的预计算技巧之一。

# Naive: O(n) per query
def range_sum_naive(nums, i, j):
    return sum(nums[i:j+1])

nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3))  # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4))  # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations

构建前缀和数组

将 prefix[i] 定义为从 nums[0] 到 nums[i-1] 的元素之和（多留出一个位置，采用从零开始、偏移 1 的索引可以简化边界情况）。通过 with 一次遍历在 O(n) 时间内构建：prefix[i] = prefix[i-1] + nums[i-1]。这样，区间查询 sum(i, j) 就变成了 prefix[j+1] - prefix[i]：只需进行一次减法，耗时 O(1)。

def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix, i, j):
    return prefix[j+1] - prefix[i]  # O(1)

nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre)                    # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3))  # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15  correct
print(range_sum(pre, 1, 3))  # 15

子数组和等于 K

查找和等于 k 的子数组数量，是一个经典的哈希映射与前缀和问题。关键洞察是：从 i 到 j 的子数组和等于 prefix[j] - prefix[i-1]。如果希望它等于 k，那么就必须满足 prefix[i-1] = prefix[j] - k。从左到右扫描并维护累计前缀和时，查找 current_sum - k 之前出现过多少次，就可以在总计 O(n) 时间内统计所有有效子数组。

from collections import defaultdict

def subarray_sum_k(nums, k):
    count = 0
    current = 0
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix
    for n in nums:
        current += n
        count += freq[current - k]  # how many prior sums give diff=k
        freq[current] += 1
    return count

print(subarray_sum_k([1, 1, 1], 2))    # 2
print(subarray_sum_k([1, 2, 3], 3))    # 2  ([1,2] and [3])

使用前缀和 with 最大子数组和

最大子数组和可以表述为一个前缀和问题：对于每个索引 j，我们希望在所有 i < j 的情况下最大化 prefix[j] - prefix[i]。对于每个 j，最优的 i 是目前见过的最小前缀和。通过从左到右扫描并跟踪 min_prefix，可以达到 O(n) 时间复杂度。这等价于从前缀和角度理解卡丹算法。

def max_subarray_prefix(nums):
    max_sum  = float('-inf')
    min_pre  = 0  # prefix[0] = 0
    current  = 0
    for n in nums:
        current += n
        max_sum = max(max_sum, current - min_pre)
        min_pre = min(min_pre, current)
    return max_sum

print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6  (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1

用于网格查询的二维前缀和

前缀和也可以扩展到二维网格。将 P[i][j] 定义为从 (0,0) 到 (i-1,j-1) 的矩形区域中所有元素的和。使用容斥公式构建：P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]。这样，任意从 (r1,c1) 到 (r2,c2) 的矩形和查询，都可以通过四次查找在 O(1) 时间内完成。

def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    P = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            P[r][c] = (P[r-1][c] + P[r][c-1]
                       - P[r-1][c-1] + grid[r-1][c-1])
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1))  # 3+0+5+6 = 14

平衡索引的累计和

平衡索引是这样一个位置：左侧元素之和等于右侧元素之和。先预计算总和，然后从左到右扫描并维护累计左侧和。右侧和为 total - left_sum - nums[i]。对每个索引在 O(1) 时间内检查是否相等，因此总体时间复杂度为 O(n)。这展示了累计和如何取代两个独立的前缀和数组。

def find_pivot_index(nums):
    total = sum(nums)
    left_sum = 0
    for i, n in enumerate(nums):
        # right_sum = total - left_sum - nums[i]
        if left_sum == total - left_sum - n:
            return i
        left_sum += n
    return -1

print(find_pivot_index([1, 7, 3, 6, 5, 6]))  # 3
print(find_pivot_index([1, 2, 3]))             # -1

除自身以外数组的乘积

给定一个数组，请返回一个数组，其中每个元素都是原数组中其他所有元素的乘积。不允许使用除法。请使用前缀乘积和后缀乘积：result[i] = （i 之前所有元素的乘积）×（i 之后所有元素的乘积）。先从左到右遍历构建前缀乘积，然后从右到左遍历，使用一个累计变量乘以后缀乘积——无需为后缀乘积额外创建数组。

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    # Left pass: result[i] = product of nums[:i]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # Right pass: multiply in product of nums[i+1:]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6]   O(n) time, O(1) extra space

前缀和 with 模运算

有些问题要求统计其和可以被 k 整除的子数组数量。使用对 k 取模的前缀和：如果 prefix[j] % k == prefix[i] % k，那么 sum(i+1..j) 就可以被 k 整除。从左到右扫描时，用哈希映射统计每个余数出现的次数，即可在 O(n) 时间内完成。关键的初始化是 freq[0] = 1，这样可以处理从索引 0 开始的子数组。

from collections import defaultdict

def subarray_div_by_k(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    current = 0
    count = 0
    for n in nums:
        current = (current + n) % k
        count += freq[current]
        freq[current] += 1
    return count

print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7  (seven subarrays divisible by 5)

用于区间更新的差分数组

差分数组是前缀和的逆运算。给定一个数组，预计算 diff[i] = nums[i] - nums[i-1]。将 x 加到区间 [l, r] 只需对差分数组执行两次 O(1) 操作：diff[l] += x 和 diff[r+1] -= x。完成所有更新后，通过一次前缀和遍历重建结果数组。这样可以将 k 次区间更新的复杂度从 O(n×k) 降低到 O(n + k)。

def apply_range_updates(n, updates):
    # updates: list of (l, r, val)
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l]   += val
        diff[r+1] -= val
    # Reconstruct with prefix sum
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]

面试问题中的前缀和

前缀和会出现在许多问题类别中：

区间查询——子数组和、矩形和
子数组计数——和等于 k、可被 k 整除
乘积问题——除自身以外的乘积
平衡问题——查找枢轴索引
区间更新——差分数组

当您看到涉及累计和或基于区间聚合的问题时，请优先考虑前缀和。它几乎总能将朴素的 O(n²) 暴力法转化为 O(n) 的解法。

# Template: prefix sum + hash map for subarray problems
from collections import defaultdict

def subarray_count_template(nums, target):
    """
    Count subarrays with property involving prefix sums.
    Adapt 'target' and lookup condition for each problem.
    """
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix at sum=0
    current = 0
    count = 0
    for n in nums:
        current += n
        count += freq[current - target]  # adjust per problem
        freq[current] += 1
    return count

print(subarray_count_template([1,2,3,2,1], 3))  # 3

累计和与累计最大值

除了前缀和之外，许多问题还会使用由单个变量 with 维护的累计最大值或累计最小值。“买卖股票的最佳时机”使用累计最低价格；从左侧计算“接雨水”时使用累计的左侧最大高度。这些模式只需要一次扫描和 O(1) 的额外空间，因此在时间和空间效率方面都是最佳范式。

def max_profit(prices):
    # Running minimum buy price
    min_price = float('inf')
    max_prof  = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_prof:
            max_prof = price - min_price
    return max_prof

def left_max_array(heights):
    # Running max from left for trapping rain water
    n = len(heights)
    left_max = [0] * n
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], heights[i])
    return left_max

print(max_profit([7,1,5,3,6,4]))  # 5

快速检查

测试您对本课“数据结构与算法——编程面试准备”相关概念的理解。

课程回顾

在本课中，您学习了：前缀和通过在一次 O(n) 遍历中预计算累计和，将 O(n) 的区间查询转换为 O(1) 的查找；将前缀和与哈希映射结合，可以在 O(n) 时间内统计和为指定值或满足可除性条件的子数组；以及差分数组是前缀和的逆运算：它支持 O(1) 的区间更新，并在最后通过一次前缀和遍历重建结果。接下来，我们将从相向指针开始学习双指针技巧。

常见问题解答