前缀和算法+实现

目录

1.前缀和算法

2.前缀和实现

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

Leetcode 304：二维区间和检索 - 数组不可变

Leetcode 560：和为K的子数组

3.总结

---

1.前缀和算法

前缀和的定义：数组从开始至某特定位置处的总和。

通过前缀和问题，我们可以计算数组的在某个区间的数值总和。其步骤如下：

（1）建立vector，用于存储前缀，并通过一定计算方式（如何计算见后续例题）计算每个位置处的前缀和。

（2）通过一定计算方式（如何计算见后续例题）计算某个区间或区域的数值总和。

2.前缀和实现

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

题目描述：

给定一个整数数组 nums，计算任意两个位置之间的数值之和。

思路：

（1）计算前缀和的方式为：sums[i] = sums[i-1] + nums[i-1]，即当前的前缀和等于上一元素的前缀和和当前元素的值的和。

（2）计算区间数值的方式为：res = sums[j+1] - sums[i]， 即区间的数值之和等于两点前缀和之差。

注意：

（1）前缀和一般都从下标为1，即第二个位置处开始记录。这是为了防止因区间下界为0而带来的越界问题。

（2）需要提前对vector的大小进行定义，以防止越界问题。（使用resize函数）

代码：

class NumArray {
public:
    vector<int>sums;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n+1);
        for(int i=1; i<=n; i++){
            sums[i] = sums[i-1]+nums[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        return sums[right+1]-sums[left];
 
    }
};

Leetcode304：二维区间和检索 - 数组不可变

题目描述：

给定一个二维矩阵 matrix，计算前缀和、区域数值和

思路：

（1）计算前缀和的方式为：sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + nums[i-1][j-1]

（2）计算区域数值和的方式为：res = sums[x2+1][y2+1] - sums[x1][y2+1] - sums[x2+1][y1] + sums[x1][y1]

注意：

（1）为防止越界，sums的所有数据从下标为1的位置开始输入

（2）由于下标的变化，注意是否需要+1 -1

代码：

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

语法：

（1）求二维vector的行数： a.size() ； 求二维vector的列数： a[0].size()

（2）重新定义二维vector的大小：a.resize(m+1,vector<int>(n+1))

Leetcode 560：和为K的子数组

题目描述：

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

思路：

（1）建立一个哈希表（unordered_map)，用于记录元素之前的前缀和出现次数。将哈希表key为0的value设置为1

（2）遍历元素一次：

        ①计算当前前缀和

        ②计算当前前缀和与目标值的差值，在hashmap中找出该差值的出现次数（即以当前遍历元素为结尾的符合条件的区间个数）

注意：

（1）本题的初始化很重要！由于没有元素时的前缀和默认为0，所以必须要提前设置。

代码：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> sums; //记录当前元素之前出现的前缀和的出现次数
        sums[0]=1; //初始化
        int pre=0, res=0;
        for(int i=0; i<nums.size();i++){
            pre += nums[i];
            res += sums[pre-k];
            sums[pre]++;
        }
        return res;
    }
};

3.总结

前缀和算法的两大重要流程是：计算前缀和、利用前缀和计算某区间或区域的值。

要注意的三大细节为：前缀和数组下标、下标对应、数组大小确定

（1）当没有元素时，前缀和默认为0，所以通常情况下，记录前缀和的数组从下标为1的地方开始记录以防止越界。这就需要特别注意原始下标和前缀和下标的对应关系，看是否需要+1或-1

（2）要注意定义的vector没有大小，要自行resize一下，防止越界

（3）560题中，要遍历元素，并记录以当前元素为上界的条件下，成立的情况个数，这就需要使用到哈希表，及时更新出现的前缀和个数。注意初始化哈希表key为0，value为1.