前缀和

前缀和为前边所有元素的和，通过两个前缀和相减，可以得到任意连续子数组的和。
前缀和的长度比数组大1，为了保证最后一个索引也拥有前缀和。

和为k的子数组

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

from collections import defaultdict
class Solution(object):
    def subarraySum(self, nums, k):
        ans = 0
        n = len(nums)
        presums = defaultdict(int)  # 这题只需要统计个数，故采用字典
        presums[0] = 1  # 初始化前缀和为0出现一次
        presum = 0
        for i in range(n):
            presum += nums[i]
            ans += presums[presum-k]
            presums[presum] += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

二维区域和检索 - 矩阵不可变/二维子矩阵的和

给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

class NumMatrix(object):
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.presum = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                self.presum[i+1][j+1] = self.presum[i][j+1] \
                + self.presum[i+1][j] - self.presum[i][j] + matrix[i][j]

    def sumRegion(self, row1, col1, row2, col2):
        return self.presum[row2+1][col2+1]-self.presum[row1][col2+1] \
        -self.presum[row2+1][col1]+self.presum[row1][col1]
1
2
3
4
5
6
7
8
9
10
11
12