• 简介
• 应用
  • 应用1：Leetcode.303
    • 题目
    • 分析
    • 代码实现
  • 应用2：Leetcode.523
    • 题目
    • 分析
    • 代码实现

简介

求区间和，一般的思路都是利用前缀和的思想。

应用

应用1：Leetcode.303

题目

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

分析

题目就可以转换为已知数组 \(nums\) ，先求前缀和 \(preSum\) ，然后再求区间和：

\(diff = preSum[right] - preSum[left -1]\)

代码实现

class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix_sums = [0 for _ in range(len(nums))]
        self.prefix_sums[0] = nums[0]
        for i in range(1, len(nums)):
            self.prefix_sums[i] = self.prefix_sums[i - 1] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        start = self.prefix_sums[left - 1] if left > 0 else 0
        return self.prefix_sums[right] - start

应用2：Leetcode.523

题目

523. 连续的子数组和

分析

设 \(preSum[i]\) 是数组 \(nums\) 的前缀和。

根据题目的条件，就可以转换为，求满足\((preSum[i] - preSum[j])\ \%\ k\ =\ 0\) 的 \((i,\ j)\) 共有多少对。

根据同余定理，若 \((preSum[i] - preSum[j])\ \%\ k\ =\ 0\) ，那么一定有：

\(preSum[i]\ \%\ k\ =\ preSum[j]\ \%\ k\)

所以，我们只需要遍历每一个前缀和，将其与 \(k\) 取模，然后看是否有相同的模，同时判断序号差值大于 \(2\) 就行了。

注意：题目中条件，\(0\) 也是 \(k\) 的倍数，所以，先提前将 \(0\) 也作为模值 \(-1\) 保存下来。

代码实现

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        diff = [0 for _ in range(length)]
        for update in updates:
            start, end = update[0], update[1]
            diff[start] += update[2]
            if end + 1 < length:
                diff[end + 1] -= update[2]

        result = [0 for _ in range(length)]
        result[0] = diff[0]
        for i in range(1, length):
            result[i] = result[i - 1] + diff[i]

        return result