基础算法(6):前缀和

发布时间:2023年12月21日

1.普通的前缀和

? ? ?我们会遇到这样的题,就是给定一个数组,求它的某一段连续子数组的和。比较传统的做法就是对于要求的区间[l,r],枚举所有的数进行相加,就像这样:

int partSum(int* arr, int l, int r)
{
	int sum = 0;
	for (int i = l; i <= r; i++)
	{
		sum += arr[i];
	}
	return sum;
}

? ? ?函数返回的是arr数组第l项到第r项的和,如果数组长度为n,这样做最坏时间复杂度为O(n),如果再有m次询问,每次询问都是O(n),时间复杂度就是O(mn)。我们接受不了这么差劲的算法,所以才有了前缀和算法思想。

2.前缀和

? ? ?前缀和是应用于顺序表,也就是数组的算法。基本思想就是我们用一个sun数组来表示数组的前缀和,就是说sum[i]表示的是前i项的和,数学公式如下:

sum[i]=a[0]+a[1]+...+a[i];
将i-1代入得到:
sum[i-1]=a[0]+a[1]+...+a[i-1];
于是有:
sum[i]=sum[i-1]+a[i];

?3.前缀和的边界值

? ? ?有了递推式,我们需要有一个边界值,一般我们会将sum[0]定义为a[0],这样下次就从sum[1]开始,就像这样:

sum[0]=a[0];
for(int i=1;i<aSize;i++)
{
   sum[i]=sum[i-1]+a[i];
}

4.前缀和的部分和

? ? ?有了前缀和和数组sum之后,我们就可以用差分法,在O(1)的时间内求到开头我们所求的部分和,因为:

 a[l]+a[l+1]+...+a[r-1]+a[r]
=(a[0]+...+a[r])-(a[0]+...+a[l-1])
=sum[r]-sum[l-1]

? ? ?所以我们只需要提前把前缀和求出来,后面每次询问都是O(1)的时间复杂度,very nice!

? ? ?还有前缀和的变形:前缀积,前缀异或和,其实思想都是一样的,后面做到题再讲

5.leetcode前缀和入门题

5.1一维数组的动态和

int* runningSum(int* nums, int numsSize, int* returnSize){
        int* res=(int*)malloc(sizeof(int)*numsSize);
        res[0]=nums[0];
        for(int i=1;i<numsSize;i++)
        {
             res[i]=res[i-1]+nums[i];
        }
        *returnSize=numsSize;
        return res;
}

? ? ?这是最简单的前缀和,就是板子题,没什么好说的。

5.2寻找数组的中心下标

int pivotIndex(int* nums, int numsSize) {
    int sum[10001];
    sum[0]=nums[0];
    for(int i=1;i<numsSize;i++)
    {
        sum[i]=sum[i-1]+nums[i];
    }
    if(sum[numsSize-1]-sum[0]==0)
    {
       return 0;
    } 
    int ans=-1;
    for(int i=1;i<numsSize;i++)
    {
        if(sum[i-1]==sum[numsSize-1]-sum[i])
        {
            ans=i;
            break;
        }
    }
    return ans;
}

? ? ?这个题要求中心下标,首先中心下标左右两边的数组元素和是相等的,,就是求部分和,我们应该想到用前缀和,首先把所有前缀和求出来,先判断示例3的情况,如果最后的前缀和和第一个元素差值为0,则说明应该返回0,然后就定义一个ans来记录中心下标,给ans赋值为-1,以便没有中心下标时直接返回ans,然后进入循环遍历查找,如果有sum[i-1]==sum[numsSize-1]-sum[i],也就是说第i个元素左侧元素之和等于右侧元素之和,那i就是中心下标,赋值给ans,直接break退出循环即可。

? ? ?要注意的是在我们求中心下标右侧元素之和时,等于sum[numsSize-1]-sum[i],而不是sum[i+1]。

5.3找出中枢整数

int pivotInteger(int n) {
    int sum[1001];
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+i;
    }
    for(int x=1;x<=n;x++)
    {
        if(sum[x]==sum[n]-sum[x-1])
        {
            return x;
        }
    }
    return -1;
}

? ? ?这个题和上一个题几乎一模一样,就不再多说了。

5.4所有奇数长度子数组的和

int sumOddLengthSubarrays(int* arr, int arrSize){
    int sum[101];
    sum[0]=arr[0];
    int n=arrSize;
    for(int i=1;i<n;i++)
    {
        sum[i]=sum[i-1]+arr[i];
    }
    int s=0;
    for(int len=1;len<=n;len+=2)
    {
      for(int l=0;l<n;l++)
      {
            int r=l+len-1;
            if(r>=n)break;
            if(l==0)s+=sum[r];
            else
            {
                s+=sum[r]-sum[l-1];
            }
      }
    }
    return s;
}

? ? ?首先这个题也是要求部分和,我们应该想到用前缀和来优化,滑动窗口也不是不行,但前缀和更有性价比。首先我们求出所有前缀和,定义s来存储所有满足条件的数组元素之和,然后我们应该先枚举长度,因为有长度为1的奇数长度的子数组,也有长度为3的,我们要一个个进行枚举,然后我们再定义起点和终点,用来求区间的部分和,判断终点是否大于数组长度,如果大于就退出本次循环,又因为当l=0时,l-1=-1超出数组下标范围,所以当l=0时直接求和即可,如果都不满足,我们就进行迭代求和,需要注意的是,我们所求的和包括下标l的元素,所以应该是sum[r]-sum[l-1],而不是sum[r]-sum[l]。

文章来源:https://blog.csdn.net/pancodearea/article/details/135128327
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。