前缀和——从LeetCode题海中总结常见套路

目录

前缀和定义

截断前缀和DP：LeetCode53.最大子序和

经典左右指针：LeetCode209.长度最小的子数组

暴力求解：超时

优雅的双指针写法一：

优雅的双指针写法二：

LeetCode.1588.所有奇数长度子数组的和

手速题：LeetCode.1732.找到最高海拔

---

 

前缀和定义

对于一个给定的数列 A, 它的前缀和数列S 是通过递推能求出来得部分和,即数列A中某个下标区间内的数的和,可以表示为前缀和相减的形式。                                 

注：前缀和的定义非常简单，但是其变形的却比较难以把握，其中的精髓思想可以理解为双指针(左右指针)，其核心关键词的是差分、累积、动态规划。具体的题目变化多端，其中不乏很多很经典的LeetCode镇店之宝，下面具体来看一看。

截断前缀和DP：LeetCode53.最大子序和

LeetCode DP 绝对经典之一，也是剑指offer里面经典题目之一，不多说了，看注释。

class Solution {
public:int maxSubArray(vector<int>& nums) {int sum = nums[0];int maxnum = nums[0];for (int i = 1; i < nums.size(); i++) {// 前缀和变形，选取前面所有的和或者从当前下标开始的和sum = max(nums[i], sum + nums[i]);// DP思想，动态维护最大的和maxnum = max(maxnum, sum);}return maxnum;}
};

经典左右指针：LeetCode209.长度最小的子数组

暴力求解：超时

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {if (nums.empty())return 0;for (int i = 1; i < nums.size(); i++) nums[i] += nums[i - 1];// for (auto elem : v)//     cout << elem << " ";int ans = nums.size();for (int i = 0; i < nums.size() - 1; i++) {for (int j = i + 1; j < nums.size(); j++) {if ((nums[j] - nums[i]) >= s)ans = min((j - i), ans);}}for (int i = 0; i < nums.size(); i++) {if (nums[i] >= s && i < ans)ans = i + 1;}if (ans == nums.size() && nums[nums.size() - 1] < s)return 0;return ans;}
};

优雅的双指针写法一：

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {if (nums.empty())return 0;int i = 0;int sum = 0, ans = 0;for (int j = 0; j < nums.size(); j++) {sum += nums[j];while (sum >= s) {ans = ans == 0 ? j - i + 1 : min(ans, j - i + 1);sum -= nums[i++];}}return ans;}
};

优雅的双指针写法二：

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {if (nums.empty())return 0;int ans = INT_MAX;int sum = 0, i = 0, j = 0;while (j < nums.size()) {sum += nums[j];while (sum >= s) {ans = min(ans, j - i + 1);sum -= nums[i++];}j++;}return ans == INT_MAX ? 0 : ans;}
};

LeetCode.1588.所有奇数长度子数组的和

class Solution {
public:int sumOddLengthSubarrays(vector<int>& arr) {// 前缀和int ans = 0;int length = arr.size();int prefix[length + 1];for (int i = 0; i < length; i++) {prefix[i+1] = prefix[i] + arr[i];}// 每次间隔两个向前取前缀和保证都是奇数数组for (int i = 0; i < length; i++) {for (int j = i; j >= 0; j-=2) {ans += (prefix[i+1] - prefix[j]);}}return ans;}
};

手速题：LeetCode.1732.找到最高海拔

class Solution {
public:int largestAltitude(vector<int>& gain) {// 前缀和，然后找到最大值点int ans = gain[0];for (int i = 1; i < gain.size(); i++) {gain[i] += gain[i - 1];ans = max(ans, gain[i]);}// 因为从海拔为0的点开始的,所以不可能是负数if (ans < 0) {return 0;}return ans;}
};