leetcode刷题的前缀和数组技巧【Python】

leetcode刷题的前缀和数组技巧【Python】

本文主要介绍前缀和数组技巧，不代表无其他解法，比如【303.区域和检索-数组不可变】可直接用切片处理sum(nums[i:j+1])，因此主要目的是训练技巧。

强烈建议大家熟悉数据结构的内容之后再去刷题，有事半功倍的效果。

下面通过三道leetcode题来具体展开：

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

题目描述： 给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）

示例：

输入：

[“NumArray”, “sumRange”, “sumRange”, “sumRange”]

[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

输出：

[null, 1, -1, -3]

解释：

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);

numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)

numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))

numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

class NumArray(object):
    def __init__(self,nums):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        n=len(self.nums)
        if n<=0:
            return
        presum=[0]*(n+1)
        for  i in range(0,n):
            #presum.append(presum[i]+self.nums[i])
            presum[i+1]=presum[i]+self.nums[i]
        return presum
    
    def sum_range(self,i,j):
        """和"""
        presum=self.pre_sum()
        return presum[j+1]-presum[i]
    
if __name__=='__main__':
    
    nums=[-2, 0, 3, -5, 2, -1]
    na = NumArray(nums)
    print(na.sum_range(2,5))

304.二维区域和检索-矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。image.png

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8

示例：

给定 matrix = [

[3, 0, 1, 4, 2],

[5, 6, 3, 2, 1],

[1, 2, 0, 1, 5],

[4, 1, 0, 1, 7],

[1, 0, 3, 0, 5]

]

sumRegion(2, 1, 4, 3) -> 8

sumRegion(1, 1, 2, 2) -> 11

sumRegion(1, 2, 2, 4) -> 12

import numpy as np

class NumMatrix(object):
    def __init__(self,nums):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        r=len(self.nums)
        c=len(self.nums[0])
        if r==0 | c==0:
            return
        presum=np.full((r+1,c+1),0)
        for  i in range(0,r):
            for j in range(0,c):
                #计算每个矩阵[0,0,i,j]的元素和
                #presum[i][j]=presum[i-1][j] + presum[i][j-1]+self.nums[i-1][j-1]-presum[i-1][j-1]
                presum[i+1][j+1] = presum[i][j+1]+presum[i+1][j]-presum[i][j]+self.nums[i][j]
        return presum
    
    def sum_region(self,row1,col1,row2,col2):
        """和"""
        presum=self.pre_sum()
        return presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1]
    
if __name__=='__main__':
    matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5]
    ]
    print(matrix)
    nm = NumMatrix(matrix)
    print(nm.pre_sum())
    print(nm.sum_region(2, 1, 4, 3))

或

class NumMatrix:

    def __init__(self, matrix):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        
        if not matrix or not matrix[0]:
            m, n = 0, 0
        else:
            m = len(matrix)
            n = len(matrix[0])
        thesum = [[0 for i in range(n+1)]for j in range(m+1)]
        for i in range(m):
            for j in range(n):
                thesum[i+1][j+1] = thesum[i][j+1]+thesum[i+1][j]-thesum[i][j]+matrix[i][j]
        return thesum


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        thesum=self.pre_sum()
        return thesum[row2+1][col2+1]-thesum[row2+1][col1]-thesum[row1][col2+1]+thesum[row1][col1]
    
if __name__=='__main__':
    matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5]
    ]
    print(matrix)
    nm = NumMatrix(matrix)
    print(nm.pre_sum())
    print(nm.sumRegion(2, 1, 4, 3))

560.和为k的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

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

输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。

数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

暴力解法

class SubAarraySum(object):
    def __init__(self,nums):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        n=len(nums)
        presum=[0]*(n+1)
        for i in range(n):
            presum[i+1]=presum[i]+self.nums[i]
            
        return presum
    
    def k_num(self,k):
        """暴力穷举"""
        res=0
        presum=self.pre_sum()
        for i in range(1,len(self.nums)+1):
            for j in range(0,i):
                if k==presum[i]-presum[j]:
                    res += 1
        return res
    
if __name__=='__main__':
    nums = [1,1,1]
    k = 2
    
    s = SubAarraySum(nums)
    print(s.pre_sum())
    print(s.k_num(k))    

前缀和数组用哈希表存储，k==presum[i]-presum[j]转变为presum[j]==presum[i]-k，可减少一层循环，降低时间复杂度

class SubAarraySum(object):
    def __init__(self,nums):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        n=len(nums)
        presum=[0]*(n+1)
        for i in range(n):
            presum[i+1]=presum[i]+self.nums[i]
            
        return presum
    
    def k_num(self,k):
        """hash"""
        res=0
        presum=self.pre_sum()
        #前缀和构造字典
        presum_dict={}
        for i in presum:
            if i in presum_dict.keys():
                presum_dict[i] += 1
            else:
                presum_dict[i] = 1
        #如果差值也在字典，以差值为key取value值
        for i in range(0,len(presum_dict)):
            sum_j=presum[i]-k
            if sum_j in presum_dict.keys():
                res += presum_dict.get(sum_j)               
        return res
    
if __name__=='__main__':
    nums = [1,1,1]
    k = 2
    
    s = SubAarraySum(nums)
    print(s.pre_sum())
    print(s.k_num(k))    

不用哈希表也可以实现，如下：

class SubAarraySum(object):
    def __init__(self,nums):
        self.nums=nums
        
    def pre_sum(self):
        """前缀和"""
        n=len(nums)
        presum=[0]*(n+1)
        for i in range(n):
            presum[i+1]=presum[i]+self.nums[i]
            
        return presum
    
    def k_num(self,k):
        """hash"""
        res=0
        presum=self.pre_sum()
        
        #去掉一个for循环
        for i in range(0,len(presum)):
            if presum[i]-k in presum:
                res += 1           
        return res
    
if __name__=='__main__':
    nums = [1,1,1]
    k = 2
    
    s = SubAarraySum(nums)
    print(s.pre_sum())
    print(s.k_num(k))