一 普通数组基础

首先，我们根据下图先了解一下什么是前缀和。

既然我们明白了前缀和是怎么回事，那我们就来看一下我们该怎么输入
先给出答案，然后再给出分析。
答案：

for (int i = 1; i <= n; i ++ ){
	cin >> a[i];
	s[i] = s[i - 1] + a[i];
}
1
2
3
4

我们通过这副图来理解一下为什么这么写代码就可以得到前缀和

到现在，我们已经解决了输入问题和前缀和的问题，下面就是我们如何利用前缀和的时候了。
我们用前缀和有一个很大的优势，就是可以快速的得到某一个区间的区间总和

前缀和的优势：以(o1)的时间复杂度得到某块区间的总和
好，我们先来看一下怎么求一个区间的和
我们用 L 和 R 分别表示区间的左右端点，
那么

好，前缀的内容就这么多啦
下面奉上我的代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], s[i] = s[i - 1] + a[i];
    
    while (m -- ){
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
    
}

何为前缀和算法？
前缀和算法，属于基础算法，一般来说没有固定的模板，但是其思路值得借鉴，我们来看一个案例就懂了
作用： 快速求一段和，一般暴力算法时间复杂度为O（n）,而现在使用前缀和的时间复杂度可降为O（1）

具体实现：
求s[ l, r ]的区间和

for(int i = 1; i <= n; i++){
	s[i] = s[i-1] + a[i];
}
printf("%d",s[r] - s[l-1]);
1
2
3
4

值得注意的一点是，我们一般将S[0] = 0,原因如下：
假设我们需要计算S【1，10】，那么S10 - S0可以直接得出，Sr - S（l-1）

二 53. 最大子数组和

1 题目

2 解题思路

这道题要求的是最大子数组和。

对于子数组通常有两种处理方法：

前缀和；
滑动窗口
由于这道题是求和的，我们可以考虑使用前缀和来处理。

通过前缀和可以确定任意一个子数组的数组和。

可以看到，子数组[i,j)的和是通过两个前缀和相减得到的。那么如果我们固定被减数 preArr[j]，那么只要减数最小，那么得到的子数组和就最大。

那么减数是什么？减数是 preArr[j] 之前出现过的前缀和。而最终得到的子数组是什么？是以 j 为右边界的和最大的子数组。

因此我们使用两个变量：

preSum： 累加当前位置的前缀和；
minPreSum： 记录当前位置之前的饿最小前缀和，初始为 0，表示子数组就是整个前缀。

图解算法过程

3 code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //最大子数组和，初始为极小值
        int res=INT_MIN;
        //当前元素之前的最小前缀和
        int minPreSum=0;
        //当前前缀和[0,1]
        int preSum=0;

        for(int num:nums)
        {
            //累加前缀和
            preSum+=num;
            //当前前缀和-最小前缀和表示以当前元素为右边界的最大子数组和
            res=max(res,preSum-minPreSum);
            //更新最小前缀和
            minPreSum=min(minPreSum,preSum);
        }
        return res;
    }
};

三 56. 合并区间

1 题目

2 解题思路

首先我们明确合并两个区间的过程是什么：

首先我们根据区间的起点做了一个排序，起点小的靠前，起点大的靠后；
其次我们根据前一个区间的终点和后一个区间的起点是否有重合，判断区间是否可以合并；
最后，合并后的区间起点一定是靠前的那个区间的起点，终点是两个区间中终点更大的那个；
从两个区间的合并过程中我们可以看出，合并区间：

根据区间起点排序；
维护一个当前合并的区间[start, end]
判断当前区间是否可以合并到当前的合并区间；可以则更新合并区间的终点，不可以这个区间作为新的一个合并区间去合并后面的区间。

3 code

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //对区间进行升序排序
        sort(intervals.begin(),intervals.end());
        //结果列表
        vector<vector<int>> res;

        //初始化合并区间的起点为首个区间的起点
        int start=intervals[0][0];
        //初始化合并区间的终点为首个区间的终点
        int end=intervals[0][1];

        int n=intervals.size();

        for(int i=0;i<n;i++)
        {
            //判断每一个区间能否加入当前合并区间，
            //由于首个区间已经是初始的合并区间，
            //因此从第二个区间开始判断
            if(intervals[i][0]>end)
            {
                //当前区间不能加入当前的合并区间，
                //记录当前合并区间。
                //以当前区间作为新的合并区间
                vector<int> ans={start,end};
                res.emplace_back(ans);

                start=intervals[i][0];
                end=intervals[i][1];
            }
            else
            {
                //当前区间加入当前的合并区间。
                //更新合并区间的终点
                end=max(end,intervals[i][1]);
            }
        }
        //补充加入最后一个合并区间
        vector<int> ans={start,end};
        res.emplace_back(ans);
        return res;
    }
};

四 56. 合并区间

1 题目

2 解题思路

3 code