Day1 2022.10.9
昨天在菜鸟教程上学习了c++的基本语法，今日准备着手开始学习算法，在labuladong公众号上开始按顺序学习，今天首先学习了前缀和数组。
前缀和
首先写出前缀和代码框架，之前总觉得框架自己理解不了，做了几道题之后方才了解框架的重要性
class PrefixSum{
public:
vector<int> prefix;
PrefixSum(vector<int> nums){
prefix.resize(nums.size()+1);
for(int i=1;i<nums.size;i++){
prefix[i]=prefix[i-1]+nums[i-1];
}
}
int query(int left,int right){
return prefix[right+1]-prefix[left];
}
}
通过例题leetcode 303学习
给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right实现 NumArray 类：
- NumArray(int[] nums) 使用数组 nums 初始化对象
- int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right])
示例：
输入：
["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))
这道题首先想到的是使用for循环将左右节点间的每一个数累加出来，进行暴力求解，思考了一下，我当时写的代码如下
#include <vector>
using namespace std;
class NumArray
{
public:
vector<int> nums;
NumArray(vector<int> &nums)
{
this->nums=nums;
}
int sumRange(int left, int right)
{
int res=0;
for(int i=left;i<=right;i++){
res+=nums[i];
}
return res;
}
};
暴力求解的算法所用内存和时长较长，此时引入前缀和的概念，计算出前面0-1、0-2、。。。、0-n的和，计算从左到右的累计和时，只需要将其前缀和做减法，例如求x[2]-x[5]之和，只需要用x[5]的前缀和减去x[2]的前缀和就可得到，不需要计算一个就调用一次for循环，减少了占用内存与运行时间，下为使用前缀和的代码：
#include <vector>
using namespace std;
class NumArray
{
public:
vector<int> sums;
NumArray(vector<int> &nums)
{
int n = nums.size();
sums.resize(n+1);
for (int i = 0; i < n; i++)
{
/* code */
sums[i+1]=sums[i]+nums[i];
}
}
int sumRange(int left, int right)
{
return sums[right+1]-sums[left];
}
};
304题是二位数组的前缀和的计算，计算和理解起来要比一维数组难一些，本质上还是田字型面积的计算，我们只需要用大的图形面积减去小的图形面积即可
题解代码如下:
#include<vector>
using namespace std;
class NumMatrix {
public:
vector <vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
int m=matrix.size();
if (m>0)
{
int n=matrix[0].size();
sums.resize(m+1,vector<int> (n+1));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sums[i+1][j+1]=sums[i+1][j]+sums[i][j+1]+matrix[i][j]-sums[i][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
}
};
560题也是有关前缀和，但是感觉有点难以理解，大概意思为把前缀和用数组保存起来，然后存储到哈希表中，有点类似于滑动窗口的题目，需要不断更新哈希表，暴力求解虽然简单且容易理解，但时间复杂度较高，换做前缀和并用哈希表优化后会节省很多空间
#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int sum=0,res=0;
unordered_map<int, int> mp;
mp[0]=1;
for (auto &m:nums)
{
sum+=m;
res+=mp[sum-k];
++mp[sum];
}
return res;
}
};