AK F.*ing leetcode 流浪计划之前缀和

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

@[toc]

一、简介

在操作数组的算法中,前缀和算法是非常常见的,也非常高效的算法。

前缀和算法是利用dp思想,保存共用的前缀和结果,达到降低求区间和、求解特定条件区间等运算的复杂度。

前缀和算法(思想)在平时的算法中非常常用,操作比较简单,代码少,好理解,好实现,学习成本低。
前缀和基础作用是求解数组区间和。同时还可以结合hash, 堆等数据结构来求解选定条件下的区间。

差分是前缀和的衍生算法,利用差分思想能O(n)复杂度实现对数组作n次区间修改后查询数组结果。

在一维数组前缀和思想基础上,可以扩展到二维数组的情况。

前缀和是一种思想,不只适用于和,也可以用来运算积,二进制运算(异或、与、或),求前缀最大(小)值等。

二、定义

原数组是arr[]。

前缀和的表现形式是一个数组preSum[]。

preSum[i] = arr[0]+arr[1]+…+arr[i]。

sum(i,j) = arr[i]+arr[i+1]+…+arr[j] , 从第i个元素到第j个元素之和。

利用preSum数组可以快速求解出sum(i,j)。

三、作用

  1. 求解区间和(积,异或等可逆运算)。
  2. 给定特定的条件求解区间或区间个数。
  3. 求解子矩阵和。
  4. 利用差分对数组区间修改,求解最终数组结果。
  5. 结合前缀和思想,求解前缀最大(小)值等数据,进而运算更复杂的问题。

四、数据定义及算法

数据定义

PreSum {
    preSum array // 数组 preSum[i]=arr[0]+arr[1]+...+arr[i]。
    // 常用有3种:
    InitPre(arr): // 初始化数据, 通过arr, 初始化preSum
    Sum(i,j):// 查询区间和
    MaxSubArray() // 求解最大(小)子段和。
}

算法描述

具体可以看这个视频,讲得很详细。

https://www.bilibili.com/video/BV1pi4y1j7si?p=1

  • 初始化preSum数组。

    当i==0, preSum[0]=arr[i],

    当i>0, preSum[i]=preSum[i-1]+arr[i]

  • 求解Sum(i, j)

    sum(i, j) = arr[i]+arr[i+1]+…+arr[j] = (arr[0]+arr[1]+…arr[i-1]+arr[i]+arr[i+1]+…+arr[j]) - (arr[0]+arr[1]+…arr[i-1]) = preSum[j] - preSum[i-1], 注意当i=0时,sum(i, j) = preSum[j]

  • MaxSubArray() 求解最大连续子段和

基本思路是:枚举每个以j为结尾的子段看哪个最优。

max(preSum[j]-preSum[x]) (x < j)

把上述公式优化一下得到 max(preSum[j]-preSum[x]) = preSum[j]-min(preSum[x]) (x < j)

这样只要保存前缀的最小值即可。

InitPre(arr): // 初始化数据
    preSum[0]=arr[0]
    for i <- 1 to n do
        preSum[i]<-preSum[i-1]+arr[i]

Sum(i,j):// 查询区间和
    if i==0 : return preSum[j]
    return preSum[j]-preSum[i-1]

MaxSubArray(): // 查询最大子段和
    MinPre<-0
    best
    for i<-0 to n do
    	best <- preSum[i]-MinPre
    	MinPre <- min(MinPre, preSum[i])
    	
    return best

五、具体实现


func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
前缀和
*/
type PreSum struct {
	preSum []int // 数组 preSum[i]=arr[0]+arr[1]+...+arr[i]。
}

// 常用有3种:
// 初始化数据, 通过arr, 初始化preSum
func (ps *PreSum) InitPre(arr []int) {
	ps.preSum = make([]int, len(arr))
	for i, v := range arr {
		if i == 0 {
			ps.preSum[0] = v
		} else {
			ps.preSum[i] = ps.preSum[i-1] + v
		}
	}
}

// 查询区间和
func (ps *PreSum) Sum(i, j int) int {
	if i <= 0 {
		return ps.preSum[j]
	}
	return ps.preSum[j] - ps.preSum[i-1]
}

//查询最大子段和
// 这里是普通情况,有时候有特殊要求,比如子段不能为空,子段有可能为负数==
func (ps *PreSum) MaxSubArray() int {
	minPre := 0
	best := 0

	for _, v := range ps.preSum {
		best = max(best, v-minPre)
		minPre = min(minPre, v)
	}

	return best
}

六、牛刀小试

练习1 最大子段和

题目链接 力扣 贪心,前缀和

题目大意

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:

输入:nums = [1]
输出:1
示例 3:

输入:nums = [0]
输出:0
示例 4:

输入:nums = [-1]
输出:-1
示例 5:

输入:nums = [-100000]
输出:-100000

提示:

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5

题目解析

根据贪心原理,枚举j, best = preSum[j] - min(preSum[x]) x<j

AC代码


func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
前缀和
*/
type PreSum struct {
	preSum []int // 数组 preSum[i]=arr[0]+arr[1]+...+arr[i]。
}

// 常用有3种:
// 初始化数据, 通过arr, 初始化preSum
func (ps *PreSum) InitPre(arr []int) {
	ps.preSum = make([]int, len(arr))
	for i, v := range arr {
		if i == 0 {
			ps.preSum[0] = v
		} else {
			ps.preSum[i] = ps.preSum[i-1] + v
		}
	}
}

// 查询区间和
func (ps *PreSum) Sum(i, j int) int {
	if i <= 0 {
		return ps.preSum[j]
	}
	return ps.preSum[j] - ps.preSum[i-1]
}

//查询最大子段和
// 这里是普通情况,有时候有特殊要求,比如子段不能为空,子段有可能为负数==
func (ps *PreSum) MaxSubArray() int {
	minPre := 0
	best := ps.preSum[0] // 至少包含一个数字,以第1个数据为初始值,后续有更优的会更新

	for _, v := range ps.preSum {
		best = max(best, v-minPre)
		minPre = min(minPre, v)
	}

	return best
}

func maxSubArray(nums []int) int {
    ps := &PreSum{}
    ps.InitPre(nums)
    return ps.MaxSubArray()
}

练习2 前缀积应用

题目链接: 238. 除自身以外数组的乘积 力扣 前缀积(前缀和思想)

题目大意

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

题目解析

output[i] = arr[0]*arr[1]*…*arr[i-1]*arr[i+1]*…*arr[n-1]

可以设置2个数组 prePro, backPro

prePro[i] = arr[0]*arr[1]*…*arr[i]

backPro[i] = arr[i]*arr[i+1]*…*arr[n-1]

output[i] = prePro[i-1] * backPro[i+1]

AC代码


func productExceptSelf(nums []int) []int {
	prePro, backPro := make([]int, len(nums)), make([]int, len(nums))

	for i, v := range nums {
		if i==0 {
			prePro[i]=v
			backPro[len(nums)-1-i]=nums[len(nums)-1-i]
		}else {
			prePro[i]=prePro[i-1]*v
			backPro[len(nums)-1-i]=nums[len(nums)-1-i]*backPro[len(nums)-1-i+1]
		}
	}

	for i:=0;i<len(nums);i++ {
		if i==0 {
			nums[i] = backPro[i+1]
		} else if i==len(nums)-1 {
			nums[i] = prePro[i-1]
		} else {
			nums[i] = prePro[i-1]*backPro[i+1]
		}
	}
	
	return nums
}

练习3 前缀最大值应用

题目链接: 直方图的水量 力扣 前缀最大值(前缀和思想)

题目大意

给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题目解析

对于每个柱子的位置来说最高水平面肯定是固定的,那么是什么决定了水平面的高度呢,从图中可以看出,柱子I上的水平面是由2边最高的柱子(取2柱最低面)决定的。

那么我们就可以先求出每个柱子的左,右2边最高的地方然后再取最小值运算。

设置preMax[],backMax[]

preMax[i]代表从0到i柱子最高的高度。

backMax[i]代表从i到len(height)-1柱子最高的高度。

第i根柱子上方的水量就是水平高度减去柱子高度 min(preMax[i-1], backMax[i+1]) -height[i] (当有水时,没水可能为负数,要特殊处理)

AC代码

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func trap(height []int) int {
	preMax, backMax := make([]int, len(height)), make([]int, len(height))

	for i, v := range height { // 一次遍历计算出 preMax,通过坐标转化计算backMax
		if i==0 {
			preMax[i]=v
			backMax[len(height)-1-i]=height[len(height)-1-i] 
		}else {
			preMax[i]=max(preMax[i-1],v)
			backMax[len(height)-1-i]=max(height[len(height)-1-i], backMax[len(height)-1-i+1])
		}
	}
	
	sum :=0
	
	for i:=1 ;i<len(height)-1;i++ {
		sum += max(0, min(preMax[i-1], backMax[i+1]) - height[i]) // 小于0时要特殊处理
	}
	
	return sum
}

练习4 查询特定条件区间

题目链接: 560. 和为K的子数组 力扣 前缀和,哈希查询

题目大意

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

题目解析

题意为求解 i,j 对数,使得sum(i,j) 区间和为k.
sum(i, j) = preSum[j]-preSum[i] = k
我们枚举 j, 然后去查询 preSum[i]= preSum[j]-k (i<j)即可。
可以设置一个hash map cnt[int]int
当遍历到一个preSum[i]时,cnt[preSum[i]]++.
这样可以快速查询到cnt[reSum[j]-k]

AC代码


func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
前缀和
*/
type PreSum struct {
	preSum []int // 数组 preSum[i]=arr[0]+arr[1]+...+arr[i]。
}

// 常用有3种:
// 初始化数据, 通过arr, 初始化preSum
func (ps *PreSum) InitPre(arr []int) {
	ps.preSum = make([]int, len(arr))
	for i, v := range arr {
		if i == 0 {
			ps.preSum[0] = v
		} else {
			ps.preSum[i] = ps.preSum[i-1] + v
		}
	}
}

// 查询区间和
func (ps *PreSum) Sum(i, j int) int {
	if i <= 0 {
		return ps.preSum[j]
	}
	return ps.preSum[j] - ps.preSum[i-1]
}

//查询最大子段和
// 这里是普通情况,有时候有特殊要求,比如子段不能为空,子段有可能为负数==
func (ps *PreSum) MaxSubArray() int {
	minPre := 0
	best := ps.preSum[0] // 至少包含一个数字,以第1个数据为初始值,后续有更优的会更新

	for _, v := range ps.preSum {
		best = max(best, v-minPre)
		minPre = min(minPre, v)
	}

	return best
}

func subarraySum(nums []int, k int) int {
	cnt := map[int]int{0: 1} // 一开始前缀和为0的算1个
	ans := 0
	
	ps := &PreSum{}
	ps.InitPre(nums)
	for i := range nums {
		s := ps.preSum[i] - k
		ans += cnt[s] // 查询以当前数字为结尾之前有多少段满足条件
		cnt[ps.preSum[i]]++ // 前缀统计+1
	}

	return ans
}

七、总结

主要内容:

  1. 介绍与实现一维情况下前缀和几种常用算法
  2. 介绍一些常用场景
  3. 结合实例说明一些具体用法

本文主要介绍一维情况,二维情况也是类似,有兴趣的可以去https://www.bilibili.com/video/BV1pi4y1j7si?p=1 这里看,讲得很好我就不重复写了,还有差分原理也讲得很清楚。

笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目(首先AK F.*ing leetcode),给大家准备了一些题目,供大家练习参考。干他F.*ing (Fighting?)。

八、实战训练

代码基础训练题

光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那2题A了。

练习1 最大子段和 题目链接 力扣 贪心,前缀和

练习2 除自身以外数组的乘积 力扣 前缀积(前缀和思想)

练习3 直方图的水量 力扣 前缀最大值(前缀和思想)

练习4 560. 和为K的子数组 力扣 查询特定条件区间 , 前缀和,哈希查询

AK leetcode

我整理了leetcode相关题目。

53. 最大子序和 贪心,前缀和

152. 乘积最大子数组 前缀和,区间求积,贪心

209. 长度最小的子数组 前缀和,给定条件查找区间,查询

238. 除自身以外数组的乘积 前缀积(前缀和思想)

303. 区域和检索 - 数组不可变 前缀和,求区间和

304. 二维区域和检索 - 矩阵不可变 前缀和,二维应用,区间求和

327. 区间和的个数 前缀和,给定条件查找区间,查询

363. 矩形区域不超过 K 的最大数值和 前缀和,贪心,二维转一维

523. 连续的子数组和 前缀和,查询

525. 连续数组 前缀和,查询,差值dp

560. 和为K的子数组 前缀和,查询

567. 字符串的排列 前缀和,区间求和,枚举

643. 子数组最大平均数 I 前缀和,区间求和

1248. 统计「优美子数组」 转化到前缀和

1423. 可获得的最大点数 区间和

1567. 乘积为正数的最长子数组长度 前缀积

1712. 将数组分成三个子数组的方案数 前缀和,区间求和,二分查找

1738. 找出第 K 大的异或坐标值 动态规划 - 前缀和 - 排序

1749. 任意子数组和的绝对值的最大值 前缀和,贪心

1763. 最长的美好子字符串 前缀和,区间求和,枚举

1781. 所有子字符串美丽值之和 前缀和,区间求和,枚举

面试题 17.21. 直方图的水量 最大前缀,枚举


做完以上还觉得不过瘾,我给大家还准备了一些。

大神进阶

也可以去vjudge Problems - Virtual Judge 搜索相关题号

hdu

Problem - 1556 差分应用

Problem - 5419 区间求和

Problem - 5147 hash, 前缀和

Problem - 5084 二维前缀和

Problem - 2089 数位dp,前缀和

Problem - 5480 前缀和

Problem - 6186 前缀运算(前缀和思想)

poj

3292 -- Semi-prime H-numbers 素数筛选,前缀和

3061 -- Subsequence 前缀和,枚举,二分

3263 -- Tallest Cow 前缀和

2796 -- Feel Good 前缀和,单调栈

1050 -- To the Max 枚举,前缀和


本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。