前缀和
- 一维数组A
- 前缀和数组S
- 子段和——A中第l个数到第r个数的和
- 当A中都是非负数时，前缀和数组S单调递增
实战
1248.统计 [优美子数组]
https://leetcode.cn/problems/count-number-of-nice-subarrays/
奇数看作1，偶数看作О，求前缀和数组S
连续子数组[Lr]中的奇数个数为S[r]-S[l一1]
枚举右端点i，只需找到i前面有多少个j满足S[i] -Si]= k
由于S单调递增，只要满足S[i]-S[ji]=k (k > 0)，j必然在i前面
所以只需用一个计数数组统计S中每个值的个数
枚举右端点i，看一下等于S[i]-k的值有几个就行了
class Solution { public: int numberOfSubarrays(vector<int>& nums, int k) { //源问题 //sum(l,r)==k int n=nums.size(); vector<int> s(n+1); s[0]=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+nums[i-1]%2; vector<int> count(n+1); int ans=0; count[s[0]]++; for(int i=1;i<=n;i++) { if(s[i]-k>=0) ans+=count[s[i]-k]; count[s[i]]++; } return ans; } };
53.最大子数组和
https://leetcode.cn/problems/maximum-subarray/
解法一:前缀和＋前缀最小值
求出前缀和数组S，枚举右端点i，需要找到i之前的一个j使得S[i]-S[]最大
也就是要让S[]最小，再维护一个S的前缀最小值即可
“前缀和”算法不只局限于求和，也可以扩展到前缀最小值、最大值等
解法二:贪心
只要“和”是正的，就不断向右扩展一旦发现“和”是负的，立即舍弃
如果需要方案，用双指针维护当前取的范围即可
class Solution { public: int maxSubArray(vector<int>& nums) { // int pre = 0, maxAns = nums[0]; // for (const auto &x: nums) { // pre = max(pre + x, x); // maxAns = max(maxAns, pre); // } // return maxAns; int n=nums.size(); vector<int> dp(n+1,0); dp[0]=nums[0]; int mmax=dp[0]; for(int i=1;i<n;i++) { dp[i]=max(nums[i],dp[i-1]+nums[i]); mmax=max(mmax,dp[i]); } return mmax; } };
二维前缀和
- 二维数组A
- 前缀和数组S
- 子矩阵和——以(p,q)为左上角、(i,j)为右下角的A的子矩阵中数的和
实战
304.二维区域和检索–矩阵不可变
https://leetcode.cn/problems/range-sum-query-2d-immutable/
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 = 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[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1]; } };
差分
- 一维数组A
- 差分数组B
- 其中B1=A1，Bi= Ai-Ai-1(2≤ i ≤n)
- 差分数组B的前缀和数组就是原数组A
- 把A的第l个数到第r个数加d，B的变化为:Bl加d，Br+1减d
实战
1109.航班预定统计
https://leetcode.cn/problems/corporate-flight-bookings/
class Solution { public: vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { vector<int> ans(n+1); for(vector<int> &booking :bookings) { ans[booking[0]-1]+=booking[2]; ans[booking[1]]-=booking[2]; } partial_sum(ans.begin(),ans.end(),ans.begin()); ans.pop_back(); return ans; } };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
