基础算法---前缀和

文章目录

基本思想
1.前缀和
2.子矩阵的和
3.长度最小的子数组
4，除自身以外数组的乘积
总结

基本思想

前缀和数组就是一个数组的前i项和
在这里插入图片描述

前缀和的用处：前缀和数组求出来之后我们就可以就可以求数组中的某个特定区间的和

就比如说求l到R的和，我们可以转换为求1到R的和减去1到l-1的和

接下来我们来做两道题，让大家感受一下

1.前缀和

这道题是一道非常经典最能代表前缀和算法的一道题

这道题的思路很简单就是根据公式s[i]=s[i-1]+a[i]然后将前缀和求出来，根据条件去输出，我们来看一下代码

#include<iostream>
using namespace std;
#define N 100010
//n个数据和m行
int n,m;
//定义一个数组和一个前缀和数组
int a[N],S[N];
//定义两个边界
int l,r;
int main()
{
	//输入
    cin>>n>>m;
    //输入
    for(int i=1;i<=n;i++)cin>>a[i];
    //将前缀和的s[0]定义为0，这样方便求出第多少到第多少的和
    S[0]=0;
    //根据公式求出前缀和
    for(int i=1;i<=n;i++)
    {
        S[i]=S[i-1]+a[i];
    }
    //根绝条件输出
    while(m)
    {
        cin>>l>>r;
        cout<<S[r]-S[l-1]<<endl;
        m--;
    }
    return 0;
}

2.子矩阵的和

这道题是二维的前缀和，我们先来讨论一下二维数组的前缀和的基本概念

对于二维数组的前缀和我们先看下图颜色标出的方块的区间
在这里插入图片描述

上面这个蓝色的区域就是二维数组的前缀和，这下我们来讨论我们该怎么求这个前缀和
在这里插入图片描述
深色区域就表示S[i-1,j]

紫色区域是S[i,j-1]，从上图不难看出中间的四个方形的区域被重复加了两次，意思说我们还要减去中间的四个方形的区域

减去黑色区域，加上红色区域最后就得到了前缀和
**公式：S[i,j]=S[i-1,j]+S[i,j-1]-S[i-1,j-1]+a[i,j]

那么下面的阴影区域怎么求呢？
在这里插入图片描述
我们可以先求S[x1,y1]
减去紫色区域

再减去深蓝色区域
在这里插入图片描述
因为左上角的深蓝色区域被减了两次，所以需要加上，最后便得到了原来的浅蓝色区域
公式：S=S[x1,y1]-S[x2-1,y1]-S[x1,y2-1]+S[x2-1,y2-1]

接下来我们直接来做上面的子矩阵的和，根据上面的公式可以直接写出代码

#include<iostream>
using namespace std;
#define N 1010
int n,m,q;
int a[N][N],s[N][N];

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}

3.长度最小的子数组

根据题目描述，我们可以先求出前缀和，然后用滑动窗口去更新每一次的最小的长度

int minSubArrayLen(int target, int* nums, int numsSize) {
    int *S=(int*)malloc(sizeof(int)*(numsSize+1));
    S[0] = 0;
    for (int i = 1;i <= numsSize;i++)
    {
        S[i] = S[i - 1] + nums[i - 1];
    }
    int min = 0;
    int l = 0;
    int r = 1;
    while (r < numsSize + 1)
    {
        if (l == r)
        {
            if (S[l] >= target)
            {
                if (min > l || min == 0)
                    min = l;
            }
            r++;
        }
        else
        {
            if (S[r] - S[l] >= target)
            {
                if (min > r - l || min == 0)
                {
                    min = r - l;
                }
                l++;
            }
            else {
                r++;
            }
        }
    }

    return min;
}

4，除自身以外数组的乘积

这道题需要排除特殊情况，特殊情况就是0，遇到零我们直接跳过，然后求出累乘，求出累乘之后，再开辟一个数组，用这个数组去存储除自身以外的所有数的乘积，首先我们需要记录一下零的个数，如果零的个数超过两个的话，数组中所有的数都会被置为零，当只有一个零的时候，除了零之外的数都是0,0对应的乘积就是剩下的数的乘积
代码展示

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    //累乘
    int sum = 1;
    //记录零的个数
    int count = 0;
    for (int i = 0;i < numsSize;i++)
    {
        //不等于0就乘到累乘中
        if (nums[i] != 0)
        {
            sum *= nums[i];
        }
        //如果是0就count++
        if (nums[i] == 0)
        {
            count++;
        }
    }
    //将*returnSize的大小用数组大小赋值
    *returnSize = numsSize;
    //创建空间
    int* newnode = (int*)malloc(sizeof(int) * (*returnSize));
    if (count >= 2)
    {
        for (int i = 0;i < (*returnSize);i++)
        {
            newnode[i] = 0;
        }
    }
    else if (count == 0)
    {
        for (int i = 0;i < (*returnSize);i++)
        {
            newnode[i] = sum / nums[i];
        }
    }
    else
    {
        for (int i = 0;i < (*returnSize);i++)
        {
            if (nums[i] == 0)
            {
                newnode[i] = sum;
            }
            else
            {
                newnode[i] = 0;
            }
        }
    }
    return newnode;
}