达州做网站
大橙子网站建设，新征程启航
为企业提供网站建设、域名注册、服务器等服务
【算法和数据结构】前缀和-创新互联
1.概念定义
1）部分和
网页名称：【算法和数据结构】前缀和-创新互联
新闻来源：http://dzwzjz.com/article/dcdgeo.html
部分和就是给定一个一个数组arr,求其中某一段连续子数组[l,r]的和。通常的做法是遍历l到r之间的元素相加，这样的作法最坏时间复杂度可以达到O(n),如果有m次访问时间复杂度达到了O(mn)。基于对上述问题的优化，我们引入前缀和的概念。我们可以声明一个数组sum，来记录数组前i项的和，可以得出递推公式sum[i]=sum[i-1]+arr[i]。有了递推公式，我们还要考虑边界值，即sum[0]的值，由于此时sum[0]=a[0]，可得出sum[-1]=0。由于代码中下标不能为-1，只要做一次i的判断就可以了。有了sum数组之后，我们就可以利用差分法，用sum[r]-sum[l-1]即可求出[l,r]区间内所有元素的和，每一次计算时间复杂度都是O(1)。例：给定一个整数数组num，请计算数组的中心下标。如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回-1。中心下标是数组的一个下标，其左侧所有元素加起来的和等于右侧所有元素加起来的和。
思想：从左往右枚举数组中的元素，计算左侧元素和与右侧元素和，若两者相等则直接返回下标。每次计算时间复杂度O(1)，总过程为O(n)。代码实现如下。
public int pivotIndex(int[] arr){int size = arr.length;
int[] sum = new int[size];
//计算前缀和
for(int i=0;isum[i] = arr[i];
if(i>0){sum[i] += sum[i-1];
}
}
//判断边界值0
if(sum[0] == sum[size-1]){return 0;
}
//遍历数组分别计算每一个元素的左侧和和右侧和
for(int i=1;iif(sum[i-1] == sum[size-1]-sum[i]){return i;
}
}
//找不到中心坐标返回-1
return -1;
} 例：给定一个整数数组num，返回输出数组output，其中output[i]为num中除num[i]外所有数的乘积。
思想：前缀和的变种，求和改为求积即可，同理的还有前缀异或和，即sum[i]=sum[i-1]^a[i]。此题的代码实现如下。
public int[] productExceptSelf(int[] arr){int size = arr.length;
int[] pre = new int[size];
//计算前缀积
for(int i=0;ipre[i] = arr[i];
if(i>0){pre[i] *= pre[i-1];
}
}
//为了方便后续计算，同时计算出后缀积
int[] post = new int[size];
for(int i=size-1;i>=0;i--){post[i] = arr[i];
if(ipost[i] *= post[i+1];
}
}
int[] result = new int[size];
//为了计算方便，这里取i-1的前缀积乘i+1的后缀积作为结果
for(int i=0;iif(i==0){result[i] = post[i+1];
}else if(i==size-1){result[i] = pre[i-1];
}else{result[i] = pre[i-1]*post[i+1];
}
}
return result;
} 给定一个整数数组arr，其初始元素都为0。然后选择一个区间[1,5]，给其中每个元素加3；在选择一个区间[3,6]，给其中每个元素加2。求此时arr中每个元素的值是多少。假设数组长度为n，总共经过m次累加操作，如果每次累加都需要遍历区间内所有元素的话，最坏情况时间复杂度为O(mn)。当在数组arr的[l,r]区间上累加一个数x时，可以在l位置加x，再在r+1的位置减x，再求前缀和，就是我们要的结果。此时每次累加操作时间复杂度为O(1)，整个过程为O(n)。例：这里有n个航班，它们分别从1到n进行编号。有一份航班预定表bookings，表中第i条记录为bookings[i]=[firsti,lasti,seatsi]，意味着在从firsti到lasti的每个航班，都预定了seatsi个座位。请你返回一个长度为n的数组，里面的元素是每个航班预定的座位总数。
思想：对每个区间[firsti,lasti]，我们在firsti的位置加seatsi，在lasti+1的位置减seatsi，最后统计前缀和就是答案。代码实现如下。
public int[] cropFlightBookings(int[][] bookings,int n){//初始化一个所有元素都是0的数组
int[] sum = new int[n+1];
//用O(1)的方式操作数组，使其满足在区间[firsti,lasti]上增加seatsi
for(int i=0;iint first = bookings[i][0];
int last = bookings[i][1];
int seats = bookings[i][2];
sum[first] += seats;
sum[last+1] -= seats;
}
int[] res = new int[n];
//对数组sum求前缀和即可求出结果
for(int i=1;ires[i-1] = sum[i];
if(i>1){res[i-1] += res[i-2];
}
}
return res;
} 上文所讲的前缀和统计用的例子都是初始为0的数组，当数组初始元素不为0则无法进行前缀和统计的操作，这种情况下，我们需要自己创造一个数组d，使它的前缀和sum[i]=arr[i]。根据前缀和的定义，我们可以递推出该数组中的元素d[i]=arr[i]-arr[i-1]。数组d就叫做arr的差分数组。在数组d上即可进行上述的前缀和统计操作。1894. 找到需要补充粉笔的学生编号
2256. 最小平均差
1737. 满足三条件之一需改变的最少字符数
2055. 蜡烛之间的盘子
文章内容为英雄哥算法星球的个人学习总结，B站英雄哥直播间：https://live.bilibili.com/24513717，每日凌晨5点到8点直播刷题。
注：本文章搬运自个人博客。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页名称：【算法和数据结构】前缀和-创新互联
新闻来源：http://dzwzjz.com/article/dcdgeo.html