| 【算法精讲】一篇让你掌握前缀和算法（附图解和不少题目练习~~） | 您所在的位置：网站首页 › 前缀homi是什么意思 › 【算法精讲】一篇让你掌握前缀和算法（附图解和不少题目练习~~） |
【算法精讲】一篇让你掌握前缀和算法（附图解和不少题目练习~~）
|
前缀和：
1.简介2.一维前缀和讲解求子矩阵内的和代码
3.二维前缀和讲解求子矩阵和代码
4.题目一维前缀和模板二维前缀和模板寻找数组的中心下标除自己以外数组的乘积和为k的子数组
1.简介
前缀和算法是一种用空间换时间的算法，他常常用于解决某些题目或者作为某些高级算法的组成部分。 例如：让你求某个矩阵（一维）的子矩阵的最大值，如果使用暴力解法它的时间复杂度将会是O(n^2) ，但如果使用该算法就可以使其时间复杂度降低一个维度也就是O(N). 2.一维前缀和 讲解该算法需要开辟一个比原数组的大小大一个内存的数组 它的每一个元素意义是：前原数组n个元素的总和。也就是说下标为3的元素，是原来前三个元素的和。（也可以理解为除了自己以外的前面元素的和） 至于为什么会多开辟一个元素，我们后续会讲。 s u m [ i ] = a r r [ i − 1 ] + s u m [ i − 1 ] sum[i]=arr[i-1] + sum[i-1] sum[i]=arr[i−1]+sum[i−1] 此时我们多开一个内存的意义就可以体现出来了，当我们求第一个元素数组的时候需要加上前一个sum 。 但是如果第一个元素前一个位置没有东西就会发生越界访问，因此我们要给他提前准备一个内存并且默认为0。 总的来说，就是为了处理第一个元素越界的问题。 求子矩阵内的和我们已经知道了sum的每一个元素的意义，那么原数组的子矩阵的和也就可以得出来，例如：下标x到y的子矩阵之和就等于：
s
o
n
=
s
u
m
[
y
+
1
]
−
s
u
m
[
x
]
son=sum[y+1]-sum[x]
son=sum[y+1]−sum[x] 如果你理解了上述内容，它的代码就可以轻松写出来： #include using namespace std; int main() { int arr[5] = {1,2,3,4,5}; int sum[6]; sum[0] = 0; for (int i = 1; i v[i][j] = j + 1;//每个一维数组初始化为1 2 3 sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v[i][j];//递推 } for (auto i : sum) { for (auto k : i) cout for (int j = 1; j cin >> x1 >> y1 >> x2 >> y2; cout vectordp(nums.size() + 1, 0); vectordp1(nums.size() + 1, 0); for (int i = 1; i dp1[i] = dp1[i + 1] + nums[i + 1]; } for (int i = 0; i public: vector productExceptSelf(vector& nums) { // int sum = accumulate(nums.begin(), nums.end(), 1, mulltiplies()); int n = nums.size(); vector ans(n); ans[0] = 1; for(int i = 1; i = 0;i--){ ans[i] = ans[i] * r; r *= nums[i]; } return ans; } }; 和为k的子数组
挺难的 思路： 感谢观众老爷的观看Thanks♪(･ω･)ﾉ，如果觉得满意的话留个关注再走吧。 |
因此我们可以得出求和数组的递推公式：
【本文地址】
公司简介
联系我们