标准模板库巧解算法题 前缀和

2021/10/26 11:10:00

本文主要是介绍标准模板库巧解算法题 前缀和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前缀和常用于解决 区域和检索 相关的题型

​ 一维的前缀和,二维的积分图,都是把每个位置之前的一维线段或二维矩形预先存储,方便加速计算。如果需要对前缀和或积分图的值做寻址,则要存在哈希表里;如果要对每个位置记录前缀和或积分图的值,则可以储存到一维或二维数组里,也常常伴随着动态规划。

303 区域和检索

设计一个类,使得其能够快速查询给定整数数组 nums中,求数组从索引 iji ≤ j)范围内元素的总和,包含 ij两点。

NumArray 类的调用样例:

输入:[“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))

解析:

​ 对于一维的数组,我们可以使用前缀和来解决此类问题。先建立一个与数组 nums 长度相同的新数组 psum,表示 nums 每个位置之前前所有数字的和。psum 数组可以通过 C++ 自带的 partial_sum 函数建立,也可以直接遍历一遍 nums 数组,并利用状态转移方程 psum[i] = psum[i-1] + nums[i] 完成统计。如果我们需要获得位置 i 和 j 之间的数字和,只需计算 psum[j+1] - psum[i] 即可。

class NumArray {
    vector<int> psum;
public:
    NumArray(vector<int>& nums) {
        psum.resize(nums.size()+1);
        partial_sum(nums.begin(),nums.end(),psum.begin()+1);
    }
    
    int sumRange(int left, int right) {
        return psum[right+1]-psum[left];
    }
};

304 二维区域和检索

设计一个类,使得其能够快速查询给定矩阵中,任意两个位置包围的长方形中所有数字的和。计算其子矩形范围内元素的总和,该子矩阵的 左上角(row1, col1)右下角(row2, col2)

NumMatrix 类的调用样例。其中 sumRegion 函数的四个输入分别是第一个点的横、纵坐标,和第二个点的横、纵坐标。

输入: [“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”] [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]

输出: [null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[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]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

解析:

​ 类似于前缀和,我们可以把这种思想拓展到二维,即积分图(image integral)。我们可以先建立一个 intergral 矩阵,intergral[i][j] 表示以位置 (0, 0) 为左上角、位置 (i, j) 为右下角的长方形中所有数字的和。
​ 如下图所示,我们可以用动态规划来计算 integral 矩阵:intergral[i][j] = matrix[i-1][j-1] + integral[i-1][j] + integral[i][j-1] - integral[i-1][j-1],即当前坐标的数字 + 上面长方形的数字和 + 左边长方形的数字和 - 上面长方形和左边长方形重合面积(即左上一格的长方形)中的数字和。

在这里插入图片描述

​ 如下图所示,假设我们要查询长方形 E 的数字和,因为 E = D − B − C + A,我们发现 E 其实可以由四个位置的积分图结果进行加减运算得到。因此这个算法在预处理时的时间复杂度为 O(mn),而在查询时的时间复杂度仅为 O(1)。

在这里插入图片描述

class NumMatrix {
    vector<vector<int>> integral;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        integral = vector<vector<int>>(m+1,vector<int>(n+1));
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                integral[i][j] = matrix[i-1][j-1] + integral[i-1][j] + integral[i][j-1] - integral[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return integral[row2+1][col2+1] - integral[row1][col2+1] - integral[row2+1][col1] + integral[row1][col1];
    }
};

307 区域和检索 - 数组可修改

线段树求解

560 和为 K 的子数组

给定一个数组,寻找和为 k 的连续区间个数。

输入一个一维整数数组和一个整数值 k;输出一个整数,表示满足条件的连续区间个数。

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

解析:

​ 本题同样是利用前缀和,不同的是这里我们使用一个哈希表 hashmap,其键是前缀和,而值是该前缀和出现的次数。在我们遍历到位置 i 时,假设当前的前缀和是 psum,那么 hashmap[psum-k] 即为以当前位置结尾、满足条件的区间个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int,int> hash;
        int psum = 0;
        hash[0] = 1; // 初始情况
        int ans = 0;
        for(auto num: nums){
            psum += num;
            ans += hash[psum-k];
            ++hash[psum];
        }
        return ans;
    }
};

参考资料

LeetCode 101:和你一起轻松刷题(C++) 第 11 章 妙用数据结构



这篇关于标准模板库巧解算法题 前缀和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程